随机算法 - HNU 13348 Finding Lines

本文主要是介绍随机算法 - HNU 13348 Finding Lines，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Finding Lines

Problem's Link: http://acm.hnu.cn/online/?action=problem&type=show&id=13348&courseid=0

Mean:

给你平面上1e5个点，让你判断是否可以找到一条直线，使得p%的点都在这条直线上。

analyse:

经典的随机算法题。

每次随机出两个点，然后对n个点进行判断，看是否有p%的点在这条直线上。

关于随机算法正确性的证明：

每次随机一个点，这个点在直线上的概率是p，p最小为20%；

随机两个点来确定一条直线，那么随机一条直线的概率就是p*p，即:4%；

也就是说，在直线上概率为0.04，不在的概率为1-0.04=0.96;

那么随机k次不在直线上的概率为0.96^k，也就是答案出现误差的概率。

这题我们随机1000次，错误的概率接近1e-18，基本是不可能事件，证毕.

Time complexity: O()

Source code:

 /* 
 * this code is made by crazyacking 
 * Verdict: Accepted 
 * Submission Date: 2015-08-02-17.06 
 * Time: 0MS 
 * Memory: 137KB 
 */ 
 #include <queue> 
 #include <cstdio> 
 #include <set> 
 #include <string> 
 #include <stack> 
 #include <cmath> 
 #include <climits> 
 #include <map> 
 #include <cstdlib> 
 #include <iostream> 
 #include <vector> 
 #include <algorithm> 
 #include <cstring> 
 #include <ctime> 
 #include <bits/stdc++.h> 
 #define  LL long long 
 #define  ULL unsigned long long 
 using namespace std; 
 const LL MAXN = 100010; 
 
 LL n , p; 
 LL x [ MAXN ], y [ MAXN ]; 
 int main() 
 { 
       srand( time( NULL ) ); 
       while( ~ scanf( "%lld %lld" , &n , &p ) ) 
       { 
             for( LL i = 0; i < n; ++ i ) 
                   scanf( "%lld %lld" , & x [ i ], & y [ i ] ); 
             if( n == 1 ) { puts( "possible" ); continue; } 
             LL sum = 0; 
             if( n * p % 100 == 0 ) sum = n * p / 100; 
             else sum = n * p / 100 + 1; 
             LL T = 1000; 
             bool flag = false; 
             while( T -- ) 
             { 
                   LL a = ( LL ) rand() * ( LL ) rand() % n; 
                   LL b = ( LL ) rand() * ( LL ) rand() % n; 
                   if( a == b ) continue; 
                   LL num = 2; 
                   for( LL j = 0; j < n; ++ j ) 
                   { 
                         if( j == a || j == b ) continue; 
                         if( ( y [ j ] - y [ a ] ) * ( x [b ] - x [ a ] ) == ( x [ j ] - x [ a ] ) * ( y [b ] - y [ a ] ) ) num ++; 
                   } 
                   if( num >= sum ) { flag = true; break ;} 
             } 
             if( flag ) puts( "possible" ); 
             else puts( "impossible" ); 
       } 
       return 0; 
 } 
 /* 
 
 */ 

另外一种据说更高效的解法：

 // Time complexity: O(n/(p/100)^2) 
 // Memory: O(n) 
 
 /* Solution method: 
  * 
  * Select 10000 (or more) pairs of points at random, and determine the lines that go through them. 
  * If 20% (or more) of all points are on the same line, we expect to find it about 400 times(*). 
  * For all lines that we find more than 230 times (at most 43), see how many points are on it. 
  * Report "possible" if one of them works. 
  * (*) Worst case: 15 points, p=20%, exactly 3 on one line: E = 10000/35 = 285.7, sigma = 16.7 
  */ 
 
 #include <algorithm> 
 #include <cmath> 
 #include <cstdio> 
 #include <map> 
 using namespace std; 
 
 const int N = 1000000; 
 const int samples = 10000 , threshold = 230; 
 
 int X [N ], Y [N ]; 
 
 int gcd ( int a , int b) 
 {     return b ? gcd(b , a %b) : a; 
 } 
 
 struct line 
 {     long long a , b , c; // ax+by=c 
     line() {} 
     // Construct line through (x1,y1) and (x2,y2) 
     line ( int x1 , int y1 , int x2 , int y2) 
     {     int d = gcd( abs( x1 - x2 ), abs( y1 - y2)); 
         if ( x1 - x2 < 0) 
             d = - d; 
         a = -( y1 - y2) / d; 
        b = ( x1 - x2) / d; 
         c = a * x1 + b * y1; 
     } 
 }; 
 
 bool operator < ( line L1 , line L2) 
 {     return L1 . a < L2 . a || ( L1 . a == L2 . a && ( L1 .b < L2 .b || ( L1 .b == L2 .b && L1 . c < L2 . c))); 
 } 
 
 map < line , int > Cnt; 
 
 // RNG (modulo 2^32) 
 unsigned int randnr() 
 {     static unsigned int rseed = 131; 
     return rseed = 22695477 * rseed + 1; 
 } 
 
 int main() 
 {     int n , p , i , j , m , s; 
     long long a , b , c; 
     map < line , int >:: iterator it; 
     // Read input 
     scanf( "%d %d" , &n , &p); 
     for ( i = 0; i < n; i ++) 
         scanf( "%d %d" , & X [ i ], & Y [ i ]); 
     // Special case: n=1 
     if (n == 1) 
     {     printf( "possible \n "); 
         return 0; 
     } 
     // Try a lot of random pairs of points 
     for (s = 0; s < samples; s ++) 
     { 
             i = randnr() % n; 
         do 
             j = randnr() % n; 
         while ( j == i); 
         Cnt [ line( X [ i ], Y [ i ], X [ j ], Y [ j ])] ++; // Add to count 
     } 
     // Check all lines whose count is above the threshold 
     for ( it = Cnt . begin(); it != Cnt . end(); it ++) 
         if ( it -> second > threshold) 
         {     a = ( it -> first ). a; 
            b = ( it -> first ).b; 
             c = ( it -> first ). c; 
             m = 0; // Count 
             for ( i = 0; i < n; i ++) 
                 if ( a * X [ i ] + b * Y [ i ] == c) 
                     m ++; 
             if ( 100 * m >= n *p) 
             {     printf( "possible \n "); 
                 return 0; 
             } 
         } 
     printf( "impossible \n "); 
     return 0; 
 } 

再附上一种二分的做法：

 #include <cstdio> 
 #include <cmath> 
 #include <set> 
 using namespace std; 
 
 const int N = 1000000; 
 
 int X [N ], Y [N ]; 
 
 int gcd ( int a , int b) 
 {     return b ? gcd(b , a %b) : a; 
 } 
 
 struct line 
 {     long long a , b , c; // ax+by=c 
     line() {} 
     // Construct line through (x1,y1) and (x2,y2) 
     line ( int x1 , int y1 , int x2 , int y2) 
     {     int d = gcd( abs( x1 - x2 ), abs( y1 - y2)); 
         if ( x1 - x2 < 0) 
             d = - d; 
         a = -( y1 - y2) / d; 
        b = ( x1 - x2) / d; 
         c = a * x1 + b * y1; 
     } 
 }; 
 
 bool operator < ( line L1 , line L2) 
 {     return L1 . a < L2 . a || ( L1 . a == L2 . a && ( L1 .b < L2 .b || ( L1 .b == L2 .b && L1 . c < L2 . c))); 
 } 
 
 set < line > findlines ( int first , int last , int p) 
 {     int mid = ( first + last) / 2; 
     int a , b , c , i , j , m; 
     set < line > S , S1; 
     if (p *( mid - first) <= 100) // Too few points left to split 
     {     for ( i = first; i < last; i ++) 
             for ( j = i + 1; j < last; j ++) 
                 S1 . insert( line( X [ i ], Y [ i ], X [ j ], Y [ j ])); 
     } 
     else 
     {     S1 = findlines( first , mid , p); 
         set < line > S2 = findlines( mid , last , p); 
         S1 . insert( S2 . begin (), S2 . end()); 
     } 
     set < line >:: iterator it; 
     for ( it = S1 . begin(); it != S1 . end(); it ++) 
     {     a = it -> a; 
        b = it ->b; 
         c = it -> c; 
         m = 0; 
         for ( i = first; i < last; i ++) 
             if ( a * X [ i ] + b * Y [ i ] == c) 
                 m ++; 
         if ( 100 * m >= p *( last - first)) 
            S . insert( * it); 
     } 
     return S; 
 } 
 
 int main() 
 {     int n , p , i; 
     scanf( "%d %d" , &n , &p); 
     for ( i = 0; i < n; i ++) 
         scanf( "%d %d" , & X [ i ], & Y [ i ]); 
     printf( "%spossible \n " , n == 1 || ! findlines( 0 , n , p ). empty() ? "" : "im"); 
     return 0; 
 } 