2739: 最远点 Time Limit: 20 Sec Memory Limit: 256 MB Description 给你一个N个点的凸多边形，求离每一个点最远的点。 Input 本题有多组数据，第一行一个数T，表示数据组数。 每组数据第一行一个数N，表示凸多边形点的个数，接下来N对数，依次表示1~N这N个点的坐标，按照逆时针给出。 Output 对于每组数据输出N个数，第i个数表示离第i个点最远的点的编号，如果有多个最远点，输出编号最小的。 Sample Input 1 4 0 0 1 0 1 1 0 1 Sample Output 3 4 1 2 HINT 数据规模和约定 坐标的绝对值在1e9以内； 任意点对距离数值的平方不会超过long long； 令S为每组数据凸多边形点数之和； 对于20%的数据，S<=2000； 对于50%的数据，S<=50000； 对于100%的数据，S<=500000； 数据有梯度。
算法讨论：
直接决策单调性，至于怎么证，因为这是个凸包。然后为什么决策点在[i, i + n]范围内是正贡献，在这个之处要取反比较，
看了下面这个图你就明白了，为了保证决策单调。
代码：
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#define stop system("pause")
using namespace std;
typedef long long ll;
const int N = 500000 + 5;
int n;
int f[N];
struct Point {
int x, y, id;
}a[N << 1];
ll sqr(int x) { return 1LL * x * x; }
bool check(int i, int j, int k) {
ll x = 1LL * sqr(a[i].x - a[j].x) + 1LL * sqr(a[i].y - a[j].y);
ll y = 1LL * sqr(a[i].x - a[k].x) + 1LL * sqr(a[i].y - a[k].y);
if(j < i || j > i + n) x = -x;
if(k < i || k > i + n) y = -y;
return x == y ? (a[j].id > a[k].id) : (x < y);
}
void solve(int l, int r, int dl, int dr) {
if(l > r) return;
int mid = l + (r - l) / 2;
int dmid = dl;
for(int i = dl; i <= dr; ++ i)
if(check(mid, dmid, i)) dmid = i;
f[mid] = a[dmid].id;
solve(l, mid - 1, dl, dmid);
solve(mid + 1, r, dmid, dr);
}
#define stone_
int main() {
#ifndef stone_
freopen("nt2012_dis.in", "r", stdin);
freopen("nt2012_dis.out", "w", stdout);
#endif
int T;
scanf("%d", &T);
while(T --) {
scanf("%d", &n);
for(int i = 1; i <= n; ++ i) {
scanf("%d%d", &a[i].x, &a[i].y);
a[i].id = i; a[i + n] = a[i];
}
solve(1, n, 1, n << 1);
for(int i = 1; i <= n; ++ i)
printf("%d
", f[i]);
//puts("");
}
#ifndef stone_
fclose(stdin); fclose(stdout);
#endif
return 0;
}