本文主要是介绍随机算法 - 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;
}
/*
*/
* 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;
}
// 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;
}
#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;
}
这篇关于随机算法 - HNU 13348 Finding Lines的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
