Finding Lines
     
    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;
}
 
随机算法 - HNU 13348 Finding Lines
原文:http://www.cnblogs.com/crazyacking/p/4696789.html