|
|
back to boardGood problem I solved this problem with O ( N ^ 2 lg N) for 1.781 sec :) Just I use finding the angle of every line with Ox, Oy, Oz. Equation of line is WRONG - O ( N ^ 3). #include<iostream> #include<cmath> #include<algorithm> using namespace std; const double eps=1e-9; struct point{long x,y,z;}; struct f { double a,b,c; bool operator==(f x) {return fabs(x.a-a)<eps&&fabs(x.b-b)<eps&&fabs(x.c-c)<eps;} }; double sqr(double t){return t*t;} bool cmp(f a,f b) { if(a.a!=b.a)return a.a-b.a<eps; else if(a.b!=b.b)return a.b-b.b<eps; else return a.c-b.c<eps; } bool cmp1(point a,point b) { if(a.x!=b.x)return a.x-b.x<eps; else if(a.y!=b.y)return a.y-b.y<eps; else return a.z-b.z<eps; } int main() { int n,mxx=-1; point a[2000]; scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z); if(n==1){cout<<1<<endl;return 0;} sort(a,a+n,cmp1); for(int i=0;i<n-1;i++) { f m[2000]; int k=0; for(int j=i+1;j<n;j++) { double d=sqrt(sqr(a[j].x-a[i].x)+sqr(a[j].y-a[i].y)+sqr(a[j].z-a[i].z)); if(d>0.0){m[k].a=(a[j].x-a[i].x)/d;m[k].b=(a[j].y-a[i].y)/d;m[k].c=(a[j].z-a[i].z)/d;k++;} } sort(m,m+k,cmp); int br1=1,mx=-1; for(int j=1;j<k;j++)if(m[j]==m[j-1])br1++;else{mx=max(mx,br1);br1=1;} mx=max(mx,br1); mxx=max(mxx,1+mx); } printf("%d\n",mxx); return 0; }
|
|
|