图像分析

## 题目大意 给出n(n<=900000)个点的坐标，求一条直线，能经过1/3的点，保证有解，只用输出一个解 ### 解法 三分之一。。。 由于期望很高。。我们可以直接rand。。rand出两个点然后进去看一遍有没有到1/3 完全可以过！ ``` #include<map> #include<ctime> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n; int x[1000000],y[1000000]; inline bool check(int i,int j) { int cnt=0; for(int k=1;k<=n;k++) if((x[i]-x[k])*(y[i]-y[j])==(x[i]-x[j])*(y[i]-y[k])) cnt++; return cnt*3>=n; } int main() { freopen("graph.in","r",stdin); freopen("graph.out","w",stdout); srand(time(NULL)); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]); int k=1; while(k<=1000) { int i=rand()%n+1,j=rand()%n+1; while(i==j) j=rand()%n; if(check(i,j)) {printf("%d %d\n",i,j);return 0;} k++; } return 0; } ```