UVALive 就是求最近的点和次近的点，直接用KD树搞。 中间用了一发判断点在多边形内的模板。
/* ***
Author :kuangbin
Created Time :2014/9/30 18:22:34
File Name :E:\2014ACM\专题学习\KD树\UVALive6014.cpp
************************************************ */
#include <stdio.h>
#include <string.h>
#include
#include
#include
#include
#include
#include
#include
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
const int MAXN = 200100;
inline long long sqr(long long x){return xx;}
struct Point{
int x,y;
Point(){}
Point(int _x,int _y){
x = _x;
y = _y;
}
long long distance(const Point &b)const{
return sqr(x-b.x)+sqr(y-b.y);
}
void input(){
scanf(“%d%d”,&x,&y);
}
Point operator -(const Point &b)const{
return Point(x-b.x,y-b.y);
}
long long operator ^(const Point &b)const{
return (long long)x\b.y - (long long)y*b.x;
}
long long operator (const Point &b)const{
return (long long)x\b.x + (long long)y*b.y;
}
};
struct Line{
Point s,e;
Line(){}
Line(Point _s,Point _e){
s = _s;
e = _e;
}
bool pointonseg(Point p){
return ((p-s)^(e-s)) == 0 && ((p-s)(p-e)) <= 0;
}
};
struct polygon{
int n;
Point p[100];
Line l[100];
void input(int _n){
n = _n;
for(int i = 0;i < n;i++)
p[i].input();
}
void getline(){
for(int i = 0;i < n;i++)
l[i] = Line(p[i],p[(i+1)%n]);
}
//2边上
//1内部
//0外部
int relationpoint(Point q){
getline();
for(int i = 0;i < n;i++)
if(l[i].pointonseg(q))
return 2;
int cnt = 0;
for(int i = 0;i < n;i++){
int j = (i+1)%n;
long long k = (q-p[j])^(p[i]-p[j]);
int u = p[i].y - q.y;
int v = p[j].y - q.y;
if(k > 0 && u < 0 && v >= 0)cnt++;
if(k < 0 && v < 0 && u >= 0)cnt–;
}
return cnt != 0;
}
}po;
namespace KDTree{
struct Point {
int x,y;
int index;
long long distance(const Point &b)const{
return sqr(x-b.x) + sqr(y-b.y);
}
};
struct qnode{
Point p;
long long dis;
qnode(){}
qnode(Point _p,long long _dis){
p = _p;
dis = _dis;
}
bool operator <(const qnode &b)const{
if(dis != b.dis)return dis < b.dis;
else return p.index < b.p.index;
}
};
priority_queue
inline bool cmpX(const Point &a,const Point &b){
return a.x < b.x || (a.x == b.x && a.y < b.y) || (a.x == b.x && a.y == b.y && a.index < b.index);
}
inline bool cmpY(const Point &a,const Point &b){
return a.y < b.y || (a.y == b.y && a.x < b.x) || (a.y == b.y && a.x == b.x && a.index < b.index);
}
bool cmp(const Point &a,const Point &b,bool div){
return div?cmpY(a,b):cmpX(a,b);
}
struct Node{
Point e;
Node \
bool div;
}pool[MAXN],*tail,*root;
void init(){
tail = pool;
}
Node *build(Point *a,int l,int r,bool div){
if(l >= r)return NULL;
Node p = tail++;
p->div = div;
int mid = (l+r)/2;
nth_element(a+l,a+mid,a+r,div?cmpY:cmpX);
p->e = a[mid];
p->lc = build(a,l,mid,!div);
p->rc = build(a,mid+1,r,!div);
return p;
}
void search(Point p,Node x,bool div,int m){
if(!x)return;
if(cmp(p,x->e,div)){
search(p,x->lc,!div,m);
if(q.size() < m){
q.push(qnode(x->e,p.distance(x->e)));
search(p,x->rc,!div,m);
}
else {
if(p.distance(x->e) <= q.top().dis){
q.push(qnode(x->e,p.distance(x->e)));
q.pop();
}
if(!div){
if(sqr(x->e.x-p.x) <= q.top().dis)
search(p,x->rc,!div,m);
}
else {
if(sqr(x->e.y-p.y) <= q.top().dis)
search(p,x->rc,!div,m);
}
}
}
else {
search(p,x->rc,!div,m);
if(q.size() < m){
q.push(qnode(x->e,p.distance(x->e)));
search(p,x->lc,!div,m);
}
else {
if(p.distance(x->e) <= q.top().dis){
q.push(qnode(x->e,p.distance(x->e)));
q.pop();
}
if(!div){
if(sqr(x->e.x-p.x) <= q.top().dis)
search(p,x->lc,!div,m);
}
else {
if(sqr(x->e.y-p.y) <= q.top().dis)
search(p,x->lc,!div,m);
}
}
}
}
void search(Point p,int m){
while(!q.empty())q.pop();
search(p,root,0,m);
}
};
Point p[MAXN];
KDTree::Point pp[MAXN];
int main()
{
int T;
scanf(“%d”,&T);
int iCase = 0;
while(T–){
iCase++;
int n;
scanf(“%d”,&n);
for(int i = 0;i < n;i++)p[i].input();
int R;
printf(“Case #%d:\n”,iCase);
scanf(“%d”,&R);
for(int r = 1; r <= R;r++){
printf(“Region %d\n”,r);
int bb;
scanf(“%d”,&bb);
po.input(bb);
int cnt = 0;
for(int i = 0;i < n;i++){
if(po.relationpoint(p[i]) > 0){
pp[cnt].x = p[i].x;
pp[cnt].y = p[i].y;
pp[cnt].index = i;
cnt++;
}
}
KDTree::init();
KDTree::root = KDTree::build(pp,0,cnt,0);
KDTree::Point o;
int m;
scanf(“%d”,&m);
while(m–){
scanf(“%d%d”,&o.x,&o.y);
KDTree::search(o,2);
if(KDTree::q.size() != 2)while(1);
KDTree::Point p2 = KDTree::q.top().p;
KDTree::q.pop();
KDTree::Point p1 = KDTree::q.top().p;
KDTree::q.pop();
printf(“%d %d\n”,p1.index+1,p2.index+1);
}
}
}
return 0;
}
