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

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

Good problem
Послано Gerasim Petrov Velchev 27 июн 2009 14:44
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;
}