---
# System prepended metadata

title: zerojudge g051 最多點的線

---

# zerojudge g051 最多點的線

https://zerojudge.tw/ShowProblem?problemid=g051

* 隨機化演算法
* *"保證最多點的那條直線上有超過 N/4 個點"*，所以隨機一個點出現在最長的線的機率是$\frac{1}{4}$，而選兩點在最長的線上的機率是$\frac{1}{4}\times\frac{1}{4}=\frac{1}{16}$
* 如果重複選一百次，錯誤機率只有$(\frac{15}{16})^{100}=0.001...$
* 選一百次，每次隨機兩個點，算有多少與其共線
* $O(n)$

```cpp=
#include <bits/stdc++.h>
#define EB emplace_back
#define vci vector<int>
#define PII pair<int,int>
#define F first
#define S second
#define rep(X, a,b) for(int X=a;X<b;++X)
#define ALL(a) (a).begin(), (a).end()
#define SZ(a) (int)(a).size()
#define NL "\n"
#define LL long long

using namespace std;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	srand(time(NULL));
	int n;
	cin>>n;
	rep(i,0,n) cin>>pt[i].F>>pt[i].S;
	LL ans=0, dx, dy;
	rep(k,0,100){
		LL a=rand()%n, b, cur=2;
		do b=rand()%n;
		while(a==b);
		dx=pt[a].F-pt[b].F, dy=pt[a].S-pt[b].S;
		rep(i,0,n){
			if(i==a || i==b) continue;
			if(dy*(pt[i].F-pt[a].F)==(pt[i].S-pt[a].S)*dx) cur++;
		}
		ans=max(ans, cur);
	}
	cout << ans << NL;
}
```