#POJ3714#Raid（不同类最小点对 + 分治）

Raid

Time Limit: 5000MS		Memory Limit: 65536K
Total Submissions: 12529		Accepted: 3701

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

一道很玄学的题，，其实我一直都这么认为，看到就会想起很久以前神犇曾经讲过的最小点对，

只是这题并不同类罢了（这个就加一个判断就好）

但是对于它的时间复杂度我其实总是深表怀疑的，尤其这个还不是同类的，

个人总感觉可以造个数据卡下去？？。。

言归正传，

明确如果在平面上放一条线，那么最小距离只有三种存在位置：全线左，全线右，跨过线

于是可以分治了。

首先将点按 x 轴排序，二分数组下标，分别先求出左半和右半的最小距离，

（按道理讲，x轴排序和y轴排序应该耗时不太一样的，这个主要看数据）

然后用这个最小距离去在mid左右找一个区间，暴力枚举区间中所有的点的距离

结束条件是当up == dn和up == dn + 1时，注意判是否同类

Code:

Status	Accepted
Time	1672ms
Memory	4888kB
Length	1660
Lang	C++
Submitted	2017-07-15 11:38:01
Shared

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

const int Max = 100000 + 5;

struct node{
    double x, y;
    bool flg;
    bool operator < (const node & X)const{
        return x < X.x;
    }
}P[Max << 1];

int X[Max << 1];

double Get_Dis(int a, int b){   return sqrt((P[a].x - P[b].x) * (P[a].x - P[b].x) + (P[a].y - P[b].y) * (P[a].y - P[b].y));}

bool cmp(int a, int b){ return P[a].y < P[b].y;}

double Get_Min(int l, int r){
    double rt = 1e100;
    if(l == r)  return rt;
    if(l + 1 == r){
        if(P[l].flg == P[r].flg)
            return rt;
        else return Get_Dis(l, r);
    }
    int mid = (l + r) >> 1;
    double L = Get_Min(l, mid);
    double R = Get_Min(mid + 1, r);
    rt = min(L, R);
    int tot = 0;
    for(int i = l; i <= r; ++ i)    if(fabs(P[i].x - P[mid].x) <= rt)
        X[++ tot] = i;
    sort(X + 1, X + 1 + tot, cmp);
    for(int i = 1; i <= tot; ++ i)
        for(int j = i + 1; j <= tot; ++ j){
            if(fabs(P[X[i]].y - P[X[j]].y) > rt)  break;
            double d = Get_Dis(X[i], X[j]);
            if(P[X[i]].flg != P[X[j]].flg && d < rt)
                rt = d;
        }
    return rt;

}

int main(){
    int T, N;
    scanf("%d", &T);
    while(T --){
        scanf("%d", &N);
        for(int i = 1; i <= N; ++ i)
            scanf("%lf%lf", &P[i].x, &P[i].y), P[i].flg = 0;
        for(int i = 1; i <= N; ++ i)
            scanf("%lf%lf", &P[i + N].x, &P[i + N].y), P[i].flg = 1;
        N <<= 1;
        sort(P + 1, P + 1 + N);
        double Ans = Get_Min(1, N);
        printf("%.3lf\n", Ans);
    }
    return 0;
}