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