Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

n*n*logn why RE?

Posted by getgoingcc at 2012-10-09 11:42:55 on Problem 1118
# 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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator