## 12311 - All-Pair Farthest Points

All about problems in Volume 123. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

bertho_coder
New poster
Posts: 1
Joined: Sat Oct 10, 2015 6:58 pm

### Re: 12311 - All-Pair Farthest Points

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

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