poj3714 Raid （分治）

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

题意:

[POJ 3714] 突袭 (Raid)

  

题目描述

  

给出A、B两个点集，每个集合包含N个点。现要求分别从两个点集中取出一个点，使这两个点的距离最小。

  

输入

  

输入的第一行包含一个整数T，表示样例个数。

接下来有T个样例，每个样例的第一行为一个整数N (1 ≤ N ≤ 100,000)，表示每个组的点的个数

随后有N行，每行有两个整数X (0 ≤ X ≤ 1,000,000,000) and Y (0 ≤ Y ≤ 1,000,000,000)，代表A组的各点的坐标。

再随后N行，每行有两个整数X (0 ≤ X ≤ 1,000,000,000) and Y (0 ≤ Y ≤ 1,000,000,000)，代表B组的各点的坐标。

  

输出

  

对于每个样例，输出两点间最小的距离，保留3位小数。注意两个点必须来自两个不同的组。

题解：

这道题可谓是分治的经典题目，将所有点按照x坐标排序，然后从中间将其分为两个部分

那么对于每个部分，它们的最小距离只会有3种情况

1.在左边部分

2.在右边部分

3.跨越了中点

于是我们就可以分治了，在套路跨越了中线的情况时，我们可以根据已经求出的最小值进行优化，

最小距离只可能在 (mid.x-min , mid.x+min)存在，y同样如此

具体实现见代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>

const int MAXN=200005;
const double inf=1e40;
using namespace std;
struct node{int x,y;bool flag;}p[MAXN];
int T,n;

bool cmp(node a,node b){
    return a.x<b.x;
}
double dist(node a,node b){
    double t1=a.x-b.x;
    double t2=a.y-b.y;
    return sqrt(t1*t1+t2*t2);
}
double divide(int s,int e){
    if(e-s<=1)
    {
        if(p[s].flag==p[e].flag) return inf;
        else return dist(p[e],p[s]);
    }
    int mid=(s+e)>>1;
    double L=divide(s,mid);
    double R=divide(mid+1,e);
    double res=min(L,R);
    double l=p[mid].x-res,r=p[mid].x+res;
    node a[1000]; int cnt=0;
    for(int i=s;i<=e;i++)
        if(l<=p[i].x&&p[i].x<=r)
            a[++cnt]=p[i];
    for(int i=1;i<=cnt;i++)
        for(int j=1;j<=cnt;j++)
            if(i!=j&&a[i].flag!=a[j].flag)
		res=min(res,dist(a[i],a[j]));
    return res;
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n); n<<=1;
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&p[i].x,&p[i].y);
            if(i>n/2) p[i].flag=1;
			else p[i].flag = 0;
        }
        sort(p+1,p+n+1,cmp);
        printf("%.3lf",divide(1,n));
        putchar(10);
    }
}