[Sdoi2010 Hide and Seek]哈密顿距离，45°、135度扫描线、树状数组

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1941
【题目大意】
给出平面上n个点。设Ki表示离i这个点的最远点的距离，与离i这个点的最近点的距离之差。
那么题目就要你求Min(Ki)。
所有距离均为哈密顿距离。
【算法分析】
首先如果我们把一个点作为原点。
那么我们发现哈密顿距离为<=2的是这个形状：
..*..
.***.
*****
.***.
..*..
我们把中间那个当原点，那么我们分开4个象限来YY。
假如说第二象限吧，
显然，哈密顿距离为2的点都在一条直线上，在这之后，哈密顿距离为3的点也都会在一条直线上~。而这条直线的倾斜角都是45°
在这直线上的点都可以表示成x-y=q。q为一个常数。（就是y=kx+b的-b啦。。。）
然后我们可以把一个点的权置为x-y。
先按x坐标从小到大排序，然后搞过来，然后要处理第二象限的话，就是在前面的点里，找y坐标>yi的点里面，x-y最小(大)的。然后这个可以用树状数组解决。
然后其它象限也是类似解决。不过1、3象限是要用倾斜角135°的直线去弄。
【其它】1A，Orz，我承认我用了外挂。。。
1 27780 edward_mj 2856K 1653MS G++ 3.30K 2010-06-04 10:19:22 2 26574 Soiliml 6488K 2386MS Pascal 4.60K 2010-05-28 21:43:28 3 25994 root 2880K 2482MS G++ 2.41K 2010-05-26 19:44:01 4 26188 hyf042 15928K 3185MS G++ 4.51K 2010-05-27 12:56:02 5 26410 jiakai 11128K 4012MS G++ 6.46K 2010-05-28 08:05:09 6 26408 jiakai 11128K 4013MS G++ 6.84K 2010-05-28 08:02:40 7 27723 michael_wind 7696K 4294MS Pascal 4.33K 2010-06-03 21:23:23 8 26405 jiakai 6008K 4310MS G++ 6.13K 2010-05-28 07:57:36 9 26845 zxytim 16184K 4325MS G++ 5.08K 2010-05-30 16:08:56 10 26406 jiakai 6008K 4340MS G++ 6.13K 2010-05-28 07:58:00 11 26209 sonicmisora 16320K 4467MS G++ 4.06K 2010-05-27 14:31:16 12 26208 sonicmisora 16320K 4467MS G++ 5.03K 2010-05-27 14:29:47 13 25996 root 8632K 4560MS G++ 3.03K 2010-05-26 19:44:52 14 26411 zxytim 6396K 4684MS G++ 4.81K 2010-05-28 08:25:29 【CODE】
#include #include #include const int N=500005;
const int INF=0x7FFFFFFF/2-79;
int n;
int ly[N],Qmin[N],Qmax[N];
struct Point{int x,y,max,min;}a[N];

void Read(int &x){
char ch=getchar();
while (!(ch>=’0′ && ch<='9')) ch=getchar();
x=0;
while (ch>=’0′ && ch<='9'){
x=x*10+ch-‘0’;
ch=getchar();
}
}

void input(){
Read(n);
int i;
for (i=1;i<=n;i++){
Read(a[i].x);
Read(a[i].y);
}
for (i=1;i<=n;i++){
a[i].max=-INF;
a[i].min=INF;
}
}

void clr(){
for (int i=1;i<=n;i++){
Qmin[i]=INF;
Qmax[i]=-INF;
}
}

int cmp(const void *A,const void *B){return *((int*)A)-*((int*)B);}
void Lisan(){
for (int i=1;i<=n;i++) ly[i]=a[i].y;
qsort(ly+1,n,sizeof(int),cmp);
}

int Findy(int x){
int l=1,r=n,mid;
while (l mid=(l+r)/2;
if (x>ly[mid]) l=mid+1;
else r=mid;
}
return l;
}

int Getmax(int p){
int res=-INF;
for (int i=p;i;i-=i&-i)
res>?=Qmax[i];
return res;
}

int Getmin(int p){
int res=INF;
for (int i=p;i;i-=i&-i)
res return res;
}

void Insmax(int p,int key){
for (int i=p;i<=n;i+=i&-i)
Qmax[i]>?=key;
}

void Insmin(int p,int key){
for (int i=p;i<=n;i+=i&-i)
Qmin[i]}

inline int max(int x,int y){return x>y?x:y;}
inline int min(int x,int y){return x if (((Point*)A)->x!=((Point*)B)->x) return ((Point*)A)->x – ((Point*)B)->x;
return ((Point*)B)->y-((Point*)A)->y;
}

void Deal_45(){
int i,y;
qsort(a+1,n,sizeof(Point),cmp45);
clr();
for (i=1;i<=n;i++){
y=n-Findy(a[i].y)+1;
a[i].max=max(a[i].max,a[i].x-a[i].y-Getmin(y));
a[i].min=min(a[i].min,a[i].x-a[i].y-Getmax(y));
Insmax(y,a[i].x-a[i].y);
Insmin(y,a[i].x-a[i].y);
}
clr();
for (i=n;i>=1;i–){
y=Findy(a[i].y);
a[i].max=max(a[i].max,Getmax(y)-(a[i].x-a[i].y));
a[i].min=min(a[i].min,Getmin(y)-(a[i].x-a[i].y));
Insmax(y,a[i].x-a[i].y);
Insmin(y,a[i].x-a[i].y);
}
}

int cmp135(const void *A,const void *B){
if (((Point*)A)->x!=((Point*)B)->x) return ((Point*)A)->x – ((Point*)B)->x;
return ((Point*)A)->y-((Point*)B)->y;
}

void Deal_135(){
int i,y;
qsort(a+1,n,sizeof(Point),cmp135);
clr();
for (i=1;i<=n;i++){
y=Findy(a[i].y);
a[i].max=max(a[i].max,a[i].x+a[i].y-Getmin(y));
a[i].min=min(a[i].min,a[i].x+a[i].y-Getmax(y));
Insmax(y,a[i].x+a[i].y);
Insmin(y,a[i].x+a[i].y);
}
clr();
for (i=n;i>=1;i–){
y=n-Findy(a[i].y)+1;
a[i].max=max(a[i].max,Getmax(y)-(a[i].x+a[i].y));
a[i].min=min(a[i].min,Getmin(y)-(a[i].x+a[i].y));
Insmax(y,a[i].x+a[i].y);
Insmin(y,a[i].x+a[i].y);
}
}

void work(){
Deal_45();
Deal_135();
}

void output(){
int res=INF;
for (int i=1;i<=n;i++)
res printf("%dn",res);
}

int main(){
input();
Lisan();
work();
output();
return 0;
}