ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1422. Светлячки

WA#18
Послано joaopfg 13 июл 2018 12:18
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