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

同为o(n ^ 2 log(n)), sort可过,map会tle

Posted by Hzj_jie at 2013-02-14 01:42:00 on Problem 1118
#include <stdio.h>
#include <map>
#include <algorithm>
//#define MAP
using namespace std;
const int MAX = 700;

int gcd(int a, int b)
{
    if(a == 0 || b == 0) return 0;
    else
    {
        if(a < 0) a = -a;
        if(b < 0) b = -b;
        if(a < b)
        {
            int c = a;
            a = b;
            b = c;
        }

        int c = a % b;
        while(c > 0)
        {
            a = b;
            b = c;
            c = a % b;
        }
        return b;
    }
}

int main()
{
    int n;
    while(scanf("%d", &n) && n)
    {
        int p[MAX][2];
        for(int i = 0; i < n; i++) scanf("%d%d", &p[i][0], &p[i][1]);
        int max = 0;
        for(int i = 0; i < n; i++)
        {
#ifdef MAP
            map<pair<int, int>, int> m;
#else
            pair<int, int> dis[MAX];
            int pos = 0;
#endif
            int same = 0;
            for(int j = i + 1; j < n; j++)
            {
                int dx = p[i][0] - p[j][0];
                int dy = p[i][1] - p[j][1];
                if(dx == 0 && dy == 0) same++;
                else
                {
                    int c = gcd(dx, dy);
                    if(c == 0)
                    {
                        if(dx == 0 && dy != 0) dy = 1;
                        else if(dy == 0 && dx != 0) dx = 1;
                    }
                    else if(c != 1 && c != -1)
                    {
                        dx /= c;
                        dy /= c;
                    }
                    if(dx < 0)
                    {
                        dx = -dx;
                        dy = -dy;
                    }
#ifdef MAP
                    m[make_pair(dx, dy)]++;
#else
                    dis[pos++] = make_pair(dx, dy);
#endif
                }
            }

#ifdef MAP
            for(map<pair<int, int>, int>::iterator it = m.begin(); it != m.end(); it++)
            {
                if((*it).second + same > max) max = (*it).second + same;
            }
#else
            sort(dis, dis + pos);
            int v = same;
            for(int i = 1; i < pos; i++)
            {
                if(dis[i] == dis[i - 1]) v++;
                else
                {
                    if(max < v) max = v;
                    v = same;
                }
            }
            if(max < v) max = v;
#endif
        }
#ifdef MAP
        printf("%d\n", max + 1);
#else
        printf("%d\n", max + 2);
#endif
    }
}

时间浪费在算最大公约数上,不过比除法安全。但是map会tle实在让人惊讶

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