UVa OJ Board

Code: Select all

#include<bits/stdc++.h>
using namespace std;
#define D(x)        cout<<#x " = "<<(x)<<endl
#define un(x)       x.erase(unique(all(x)), x.end())
#define sf(n)       scanf("%d", &n)
#define sff(a,b)    scanf("%d %d", &a, &b)
#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
#define pb          push_back
#define mp          make_pair
#define xx          first
#define yy          second
#define sqr(x)      ((LL)(x)*(x))
#define MAX         100000
typedef long long int LL;

struct point{
    int x, y;
    point(){}
    point(int _x, int _y):x(_x),y(_y){}
}pnt[MAX+11];

LL distll(point a, point b) {return sqr(a.x-b.x) + sqr(a.y-b.y);}

int match[MAX+11];

int main()
{
    //freopen("c:\\Users\\User\\Desktop\\in.txt", "r", stdin);
    //freopen("c:\\Users\\User\\Desktop\\out.txt", "w", stdout);

    int i, j, k, n, nj;
    int lo, hi, midl, midr;
    LL mx;

    while(sf(n) == 1 && n)
    {
        for(i = 0; i < n; i++)
            sff(pnt[i].x, pnt[i].y);


        mx = 1;
        for(i = 2; i < n; i++)
            if(distll(pnt[0], pnt[i]) > distll(pnt[0], pnt[mx]))
                mx = i;

        match[0] = mx;

        for(i = 1, j = mx; i < n; i++)
        {
            while(true)
            {
                nj = (j+1)%n;
                if(distll(pnt[i], pnt[j]) < distll(pnt[i], pnt[nj])) j = nj;
                else if(distll(pnt[i], pnt[j]) == distll(pnt[i], pnt[nj]) && nj < j) j = nj;
                else break;
            }

            match[i] = j;
        }

        for(i = n-1, j = match[0]; i > 0; i--)
        {
            while(true)
            {
                nj = ((j-1)%n+n)%n;
                if(distll(pnt[i], pnt[j]) < distll(pnt[i], pnt[nj])) j = nj;
                else if(distll(pnt[i], pnt[j]) == distll(pnt[i], pnt[nj]) && nj < j) j = nj;
                else break;
            }

            match[i] = min(match[i], j);
        }

        for(i = 0; i < n; i++)
            printf("%d\n", match[i] + 1);
    }
    return 0;
}