It is not said in the condition that the points have different coordinates. Can points have the same coordinates?

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)?

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

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.

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;
}

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!!!

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"...