[POJ3714] Raid 计算几何

Raid

Time Limit: 5000MS		Memory Limit: 65536K
Total Submissions: 15845		Accepted: 4429

Description

After successive failures in the battles against the Union, the Empire retreated to its last stronghold. Depending on its powerful defense system, the Empire repelled the six waves of Union's attack. After several sleepless nights of thinking, Arthur, General of the Union, noticed that the only weakness of the defense system was its energy supply. The system was charged by N nuclear power stations and breaking down any of them would disable the system.

The general soon started a raid to the stations by N special agents who were paradroped into the stronghold. Unfortunately they failed to land at the expected positions due to the attack by the Empire Air Force. As an experienced general, Arthur soon realized that he needed to rearrange the plan. The first thing he wants to know now is that which agent is the nearest to any power station. Could you, the chief officer, help the general to calculate the minimum distance between an agent and a station?

Input

The first line is a integer T representing the number of test cases.
Each test case begins with an integer N (1 ≤ N ≤ 100000).
The next N lines describe the positions of the stations. Each line consists of two integers X (0 ≤ X ≤ 1000000000) and Y (0 ≤ Y ≤ 1000000000) indicating the positions of the station.
The next following N lines describe the positions of the agents. Each line consists of two integers X (0 ≤ X ≤ 1000000000) and Y (0 ≤ Y ≤ 1000000000) indicating the positions of the agent. 　

Output

For each test case output the minimum distance with precision of three decimal placed in a separate line.

Sample Input

2
4
0 0
0 1
1 0
1 1
2 2
2 3
3 2
3 3
4
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0

Sample Output

1.414
0.000

Source

POJ Founder Monthly Contest – 2008.12.28, Dagger

题目背景翻译：

国在与工会的斗争中连续失败后，帝国撤退到最后的堡垒。帝国依靠其强大的防御体系击退了工会发动的六次浪潮。经过几个不眠之夜的思考，联邦总干事亚瑟注意到，防御系统的唯一弱点是能源供应。这个系统是由N个核电站充电的，而其中任何一个都会破坏系统。

将军很快就开始向驻扎在据点的特工发动突袭。不幸的是，由于帝国空军的进攻，他们未能到达预期的位置。作为一个有经验的将军，亚瑟很快意识到他需要重新安排计划。他现在想知道的第一件事是哪家代理商离任何发电站最近。大副能帮将军计算一个特工和一个车站之间的最小距离吗？

题解：

这是一道很经典的计算几何题目。此题的原型其实是平面最近点对，几乎算是一道模板题。唯一的不同就是当两个点同时是人或车站时，我们把他们的距离看作是正无穷大。

那么平面最近点对的nlogn做法究竟怎么做到的呢？

我们先将所有点按x坐标升序排序一遍。然后考虑分治，对于当前要处理的[l,r]区间内的所有点（若l==r返回INF），我们将其按照横坐标均分为一半对一半，并在他们直接划出一条分界线。左右两边各自算出其包含范围内的最小值，然后怎么合并两边的点呢？我们算出左右两边的最小值分别为d1 , d2（递归处理）。我们再设一个d=min(d1,d2)。很明显，左右两边的点只有到分界线距离在d以内才有机会更新最小值，而且我们还能发现这样的点不超过8个，可以很大程度缩小搜索范围。于是我们就在很短的时间内合并成功了！

AC代码：

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#define ll long long
#define ii register int
using namespace std;
const int Maxn=200005;
struct node{
    ll x,y;
    bool f;
}a[Maxn];
int n,tmp[Maxn];ll inf;
inline ll dis(node s1,node s2){
	if(s1.f==s2.f)return inf;
    return (s1.x-s2.x)*(s1.x-s2.x)+(s1.y-s2.y)*(s1.y-s2.y);
}
inline ll mn(ll x,ll y){
    return x<y?x:y;
}
inline ll ab(ll x){
    return x>0?x:-x;
}
bool cmp(node s1,node s2){
    if(s1.x!=s2.x)return s1.x<s2.x;
    return s1.y<s2.y;
}
inline ll merge(int l,int r){
    ll d=inf;
    if(l==r)return d;
    if(l+1==r)return dis(a[l],a[r]);
    int mid=l+r>>1,k=0;
    ll d1=merge(l,mid);
	ll d2=merge(mid+1,r),dt;
    d=mn(d1,d2);
    for(ii i=mid;i<=r;++i){
    	dt=a[mid].x-a[i].x;
        if(dt*dt<=d){
            tmp[++k]=i;
        }
    }
	for(ii i=mid;i>=l;--i){
    	dt=a[mid].x-a[i].x;
        if(dt*dt<=d){
            tmp[++k]=i;
        }
    }
    for(ii i=1;i<=k;++i){
        for(int j=i+1;j<=k;++j){
            d=mn(d,dis(a[tmp[i]],a[tmp[j]]));
        }
    }
    return d;
}
inline ll read(){
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){
        x=x*10;x=x+c-'0';c=getchar();
    }
    return x*f;
}
void work(){
	scanf("%d",&n);
	for(ii i=1;i<=n;++i){
		a[i].x=read();a[i].y=read();
		a[i].f=1;
	}
	for(ii i=1;i<=n;++i){
		a[i+n].x=read();a[i+n].y=read();
		a[i+n].f=0;
	}
	sort(a+1,a+1+2*n,cmp);
	printf("%.3lf\n",sqrt(double(merge(1,n*2)))); 
}
int main(){
    inf=1000000000000000000ll;
    int t;
    scanf("%d",&t);
    while(t--){
    	work();
	}
    return 0; 
}