Pair Of Lines Codeforces 961D (随机）-白红宇

Pair Of Lines Codeforces 961D (随机）

阅读量：4616 次

发布时间：2019-06-09

本文共 1305 字，大约阅读时间需要 4 分钟。

题意：给你n个点，问能不能找两条直线经过所有点

题解：打比赛的时候很傻逼的认为要确定一条一条直线必须要斜率和截距，但是我tm是在枚举与点i的连线啊啊啊啊，点i是固定的所以只要斜率相等就能判断是不是同一条直线。随机算法随机找两个点确定一条直线，如果枚举的点不在该直线上则将它加入到vector中，如果不在点上的直线超过1个，则以vector中的第一个点和第二点作为第二条直线，枚举vector中的点，如果某一点仍然不在第二条直线上，则直接说明该选点不成立，继续随机。如果随机时间超过1.7s仍然没有跑出yes则直接判断他是错误的。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include
               
                //CLOCKS_PER_SEC#define se second#define fi first#define ll long long#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define Pii pair
                
                 #define Pli pair
                 
                  #define ull unsigned long long#define pb push_back#define fio ios::sync_with_stdio(false);cin.tie(0)const double Pi=3.14159265;const double e=2.71828182;const int N=1e5+5;const ull base=163;const int INF=0x3f3f3f3f;using namespace std;pair
                  
                   p[N];vector
                   
                    vec;bool same(int i,int j,int k){ return (p[j].fi-p[i].fi)*(p[k].se-p[i].se)-(p[k].fi-p[i].fi)*(p[j].se-p[i].se);}int main(){ fio; srand(time(0)); ll n; cin>>n; for(int i=0;i
                    
                     >p[i].fi>>p[i].se; if(n<=4)return cout<<"YES\n",0; while(clock()<1.7*CLOCKS_PER_SEC){ ll t1,t2; do{ t1=rand()%n; t1=(t1*RAND_MAX+rand())%n; t2=rand()%n; t2=(t2*RAND_MAX+rand())%n; }while(t1==t2); //cout<
                     
                      <<" "<
                      
                       <

转载于:https://www.cnblogs.com/Mrleon/p/8724535.html

你可能感兴趣的文章