Re: 12311 - All-Pair Farthest Points
Posted: Sat Oct 10, 2015 7:01 pm
Getting WA
Don't know why.
My approach was to run two sliding windows from two sides to get the smallest index of the farthest point

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;
}