Don't know why.
My approach was to run two sliding windows from two sides to get the smallest index of the farthest point
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;
}