It is not said in the condition that the points have different coordinates. Can points have the same coordinates? There are no duplicate points in tests. i think test set is not full. my AC soulution uses floating arithmetic and does not work correctly on tests like 3 0 0 0 1 1 1 100000 100000 99999 right answer should be 2? Someone can give some test case to help with WA18, please? Code: #include <bits/stdc++.h> using namespace std; #define MAXN 2010 #define INF -1 typedef long long int lli; typedef pair<lli,lli> ii; typedef pair<ii,ii> pp; lli gcd(lli a,lli b){ if(a<0) a=-a; if(b<0) b=-b; if(b==0) return a; else return(gcd(b,a%b)); } int maxPoint = 1,curMax, overlapPoints, xLine, yLine, zLine; map<pp,int> slopeMap; int main(){ int n; //int x[MAXN],y[MAXN],z[MAXN]; lli x[MAXN],y[MAXN],z[MAXN]; scanf("%d",&n); //for(int i=1;i<=n;i++) scanf("%d%d%d",&x[i],&y[i],&z[i]); for(int i=1;i<=n;i++) scanf("%lld%lld%lld",&x[i],&y[i],&z[i]); if(n==1) printf("%d\n",maxPoint); else{ maxPoint = 0; for(int i=1;i<n;i++){ curMax = overlapPoints = xLine = yLine = zLine = 0; for(int j=i+1;j<=n;j++){ //int xDif = x[j] - x[i]; //int yDif = y[j] - y[i]; //int zDif = z[j] - z[i]; lli xDif = x[j] - x[i]; lli yDif = y[j] - y[i]; lli zDif = z[j] - z[i]; if(xDif == 0 && yDif == 0 && zDif == 0) overlapPoints++; else if(xDif == 0 && yDif == 0) zLine++; else if(xDif == 0 && zDif == 0) yLine++; else if(yDif == 0 && zDif == 0) xLine++; else if(xDif == 0){ //int num1 = abs(yDif); //int den1 = abs(zDif); //int yz = gcd(num1,den1); lli num1 = abs(yDif); lli den1 = abs(zDif); lli yz = gcd(num1,den1); num1 /= yz; den1 /= yz; if((yDif > 0 && zDif > 0) || (yDif < 0 && zDif < 0)){ slopeMap[make_pair(make_pair(num1,den1),make_pair(0,0))]++; curMax = max(curMax,slopeMap[make_pair(make_pair(num1,den1),make_pair(0,0))]); } else{ slopeMap[make_pair(make_pair(-num1,den1),make_pair(0,0))]++; curMax = max(curMax,slopeMap[make_pair(make_pair(-num1,den1),make_pair(0,0))]); } } else if(yDif == 0){ //int num1 = abs(xDif); //int den1 = abs(zDif); //int xz = gcd(num1,den1); lli num1 = abs(xDif); lli den1 = abs(zDif); lli xz = gcd(num1,den1); num1 /= xz; den1 /= xz; if((xDif > 0 && zDif > 0) || (xDif < 0 && zDif < 0)){ slopeMap[make_pair(make_pair(num1,den1),make_pair(INF,INF))]++; curMax = max(curMax,slopeMap[make_pair(make_pair(num1,den1),make_pair(INF,INF))]); } else{ slopeMap[make_pair(make_pair(-num1,den1),make_pair(INF,INF))]++; curMax = max(curMax,slopeMap[make_pair(make_pair(-num1,den1),make_pair(INF,INF))]); } } else if(zDif == 0){ //int num1 = abs(xDif); //int den1 = abs(yDif); //int xy = gcd(num1,den1); lli num1 = abs(xDif); lli den1 = abs(yDif); lli xy = gcd(num1,den1); num1 /= xy; den1 /= xy; if((xDif > 0 && yDif > 0) || (xDif < 0 && yDif < 0)){ slopeMap[make_pair(make_pair(INF,INF),make_pair(num1,den1))]++; curMax = max(curMax,slopeMap[make_pair(make_pair(INF,INF),make_pair(num1,den1))]); } else{ slopeMap[make_pair(make_pair(INF,INF),make_pair(-num1,den1))]++; curMax = max(curMax,slopeMap[make_pair(make_pair(INF,INF),make_pair(-num1,den1))]); } } else{ lli num1 = xDif*xDif + yDif*yDif; lli den1 = zDif*zDif; //int num2 = abs(xDif); //int den2 = abs(yDif); lli num2 = abs(xDif); lli den2 = abs(yDif); lli gcd1 = gcd(num1,den1); lli gcd2 = gcd(num2,den2); //int gcd2 = gcd(num2,den2); num1 /= gcd1; den1 /= gcd1; num2 /= gcd2; den2 /= gcd2; if((xDif < 0 && yDif > 0 && zDif > 0) || (xDif > 0 && yDif < 0 && zDif > 0)){ slopeMap[make_pair(make_pair(num1,den1),make_pair(num2,den2))]++; curMax = max(curMax,slopeMap[make_pair(make_pair(num1,den1),make_pair(num2,den2))]); } else if((xDif < 0 && yDif < 0 && zDif < 0) || (xDif > 0 && yDif > 0 && zDif < 0)){ slopeMap[make_pair(make_pair(-num1,den1),make_pair(-num2,den2))]++; curMax = max(curMax,slopeMap[make_pair(make_pair(-num1,den1),make_pair(-num2,den2))]); } else if((xDif < 0 && yDif < 0 && zDif > 0) || (xDif > 0 && yDif > 0 && zDif > 0)){ slopeMap[make_pair(make_pair(num1,den1),make_pair(-num2,den2))]++; curMax = max(curMax,slopeMap[make_pair(make_pair(num1,den1),make_pair(-num2,den2))]); } else if((xDif < 0 && yDif > 0 && zDif < 0) || (xDif > 0 && yDif < 0 && zDif < 0)){ slopeMap[make_pair(make_pair(-num1,den1),make_pair(num2,den2))]++; curMax = max(curMax,slopeMap[make_pair(make_pair(-num1,den1),make_pair(num2,den2))]); } } curMax = max(curMax,xLine); curMax = max(curMax,yLine); curMax = max(curMax,zLine); } maxPoint = max(maxPoint,curMax + overlapPoints + 1); slopeMap.clear(); } printf("%d\n",maxPoint); } return 0; } Edited by author 13.07.2018 15:13 I am getting WA at 6 using floating arithmatic. Can someone please provide any test for test # 6? My solution is O(n^2*logn) and works ~1.7 seconds. But some people got AC in .078. How? Hi! I am trying to solve this problem with hashing, but my method use gcd so the complexity is O(n^2 log n). What hash-function i must use for hashing vector (vx,vy,vz)? I used the following: abs(dx) + 5*(abs(dy) + 5*dz) dz >= 0 always, for dz=0 dy>=0 always, for dz=0 and dy=0 dx>=0 always It is base-5 representation of |dx|, |dy|, |dz|. 5 is a good multiplier because it may turn into LEA EAX, [EAX*4+EAX] in assembler which is pretty fast. I still had TL18 when I ran main loops for 1..n x 1..n. Then I changed algo to run for 1..n x i+1..n, and got AC in 1.7 sec. No floats or int64. But function (dx,dy,dz) -> abs(dx) + 5*(abs(dy) + 5*dz) is not biection I didn't get it. Could you explain more? My integral implementation finally got AC. For those who struggle with TL#9, you could change binary GCD to plain Euclidian algorithm with modulus, strangely it is a way faster despite it uses division. Edited by author 02.04.2013 02:31 try this: input: 8 0 0 0 0 0 1 0 1 0 1 0 0 1 1 0 0 1 1 1 0 1 1 1 1 output: 2 GOOD LUCK!!! 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; }
One of my solutions gets AC but cannot pass this test: 5 0 0 -1 0 0 -2 0 0 3 0 0 4 0 0 5 It answers 4, but correct answer is 5. Give me some tests I have no tests, but it could be overflow or wrong compare function I had WA5 when I performed sort for X/Y and X/Z only. Adding sorting for Y/Z as well led to TL9 at least. I think that flipping X/Y around origin to make Y>=0 and flipping X/Z around origin to make Z>=0 later cannot be done independently, or there is some other problem of this type. My prog got ac, but haven't passed this test: 4 1 1 1 1 1 1 1 1 1 1 1 2 correct answer - 4, answer of my prog - 2. It is obvious two objects can not be located at one point (otherwise we'd mention it in the statement). But if you have some new correct tests, you may send them to dimanyes@gmail.com, and we will add them into the test set. (usually authors care to mention only the opposite :) For people who will solve this problem in the future: it is possible to use floating point arithmetics and get AC with n^2*logn solution. but it gives WA 1:( could somebody find error in my source code or just offer some effective tests where my program fails here is solution #include <cstdio> #include <algorithm> using namespace std; #define MAX_SIZE 2005 struct point { int x, y, z; point(){}; point(int _x,int _y,int _z):x(_x),y(_y),z(_z){}; } mas[MAX_SIZE],tmp[MAX_SIZE]; bool operator==(point & a,point & b) { return ((a.x==b.x)&&(a.y==b.y)&&(a.z==b.z)); } int n; int gcd(int a,int b) { if (b==0) return a; else gcd(b,a%b); } void input() { scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d%d%d",&mas[i].x,&mas[i].y,&mas[i].z); } bool cmp(point & a,point & b) { if (a.x<b.x) return true; else if (a.x==b.x) if (a.y<b.y) return true; else if (a.y==b.y) return (a.z<b.z); return false; } point GetPoint(int i,int j) { point first = mas[i]; point second = mas[j]; first.x = second.x - first.x; first.y = second.y - first.y; first.z = second.z - first.z; int GCD = gcd(gcd(first.x,first.y),first.z); if (GCD!=0) { first.x /= GCD; first.y /= GCD; first.z /= GCD; } return first; } int Calc(int yk) { if (!yk) return 0; int maxAmount = 0; int cur = 1; for(int i=1;i<yk;i++) if (tmp[i]==tmp[i-1]) cur++; else { if (cur>maxAmount) maxAmount = cur; cur = 1; } if (cur>maxAmount) maxAmount = cur; return maxAmount; } void solve() { point base; int maxAmount = -1; for(int i=0;i<n;i++) { int yk = 0; for(int j=0;j<n;j++) if (i!=j) tmp[yk++] = GetPoint(i,j); sort(tmp,tmp+yk,cmp); int cur = Calc(yk) + 1; if (cur>maxAmount) maxAmount = cur; } printf("%d",maxAmount); } int main() { #ifndef ONLINE_JUDGE freopen("input.txt","rt",stdin); freopen("output.txt","wt",stdout); #endif input(); solve(); return 0; } now it's tle 18 i just substituted this lines int gcd(int a,int b) { if (b==0) return a; else gcd(b,a%b); } to int gcd(int a,int b) { if (b==0) return a; else return gcd(b,a%b); } Hello! I've WA #2. Could anybody help me with this test??? I have written 2 algos already: first - O( n^3 ) - TLE #9 second - O( n^2 * log( n^2 ) ) - also TLE #9 I don't know what to do... Please help!!! it's very strange, because I solved this problem and my AC-algo O(n^2*log(n)) has time - 0.859. Some of O(n^2logn) programs got AC and some not. But O(n^2) programs will be quicker of course. I wrote O(N^2*logN), but still TLE 9 :( I got AC with algo O ( n^2 * log( n ) ) I avoided all operations with fractional numbers. I want to know more efficient algos. Especially solutions of Walrus and currently unnamed... Can you tell about it? Thanks Bye. P.S. Maybe we'll discus this problem - everyone discribes his algo with his optimizations? P.P.S sorry for BAD English :-) Edited by author 12.04.2006 20:27 Try to avoid all division operations. It could speed up your program :) I got AC with algo O ( n^2 * log( n ) ) I avoided all operations with fractional numbers. I want to know more efficient algos. Especially solutions of Walrus and currently unnamed... Can you tell about it? Thanks Bye. P.S. Maybe we'll discus this problem - everyone discribes his algo with his optimizations? you first. How do it in O(N^2 * log(N)) ? Edited by author 03.09.2006 21:37Hi, my algo is O(N^2lg(N)) using stl map, but it runs very slowly. I am actually doing this: for every point, I move this point at position (0,0,0) and then sort the other points by the angle they have with Ox, Oy and Oz(I think this angles are called directory cosine) (I am using NO float point arithmetic to do this)... could someone help me, where could I optimize more ??? It can be done in O(n^2) with hash table instead of sorting. For future solvers. DO NOT USE MAPS HERE. O(n^2 * ln n) get AC in 1.5 with vector normalisation and full floating points arithmetic. From the statement: "(-1000000<=X[i], Y[i], Z[i]<=1000000" But simple testbug checker: for i := 1 to n do if (abs(p[i].x)>1000000) or (abs(p[i].y)>1000000) or (abs(p[i].z)>1000000) then ole; gives verdict "Output limit exceeded". So, in the test #9 some coordinates are too big. Yhis is VERY bad, because, for example, my hash function causes "Crash"... Fixed. Problem statement updated. Now -10000000<=X[i], Y[i], Z[i]<=10000000 |
|