| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
n*n*logn why RE?# include <stdio.h>
# include <algorithm>
# define N 705
int n;
int x[N], y[N], dx[N], dy[N], r[N];
int Max(int x, int y) {return x>y ? x:y;}
int eql(int i, int j)
{
if (dx[i]*dy[j] == dx[j]*dy[i])
return 1;
return 0;
}
bool cmp(int ii, int jj)
{
int i = r[ii];
int j = r[jj];
return (dx[j]*dy[i] - dx[i]*dy[j])*dx[i]*dx[j] < 0;
}
int main()
{
int i, j, st, ans;
while (scanf("%d", &n), n)
{
ans = 0;
for (i = 0; i < n; ++i)
scanf("%d %d", &x[i], &y[i]);
for (i = 0; i < n; ++i)
{
for (j = 0; j < n; ++j)
{
r[j] = j;
dx[j] = x[j] - x[i];
dy[j] = y[j] - y[i];
}
std::sort(r, r+n, cmp);
st = 0;
for (j = 1; j < n; ++j)
{
if (!eql(r[j], r[st]))
{
ans = Max(ans, j - st);
st = j;
}
}
}
printf("%d\n", ans);
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator