POJ 3714 Raid（分治）

题目链接：http://poj.org/problem?id=3714

Raid
Time Limit: 5000MS
Memory Limit: 65536K
Total Submissions: 13378
Accepted: 3867

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个点，求最近点对距离。

思路：先将所有点按x排序，将点按照横坐标用虚线分成两半，只有离虚线最近的点可能是最近点对。再将每一半的点继续分成两半，全部分成子问题。对于每个子问题，用双指针扫描，判断距离。事实上每个点可能最近点只有“日”顶点的这六个点。因为懒。。。直接暴力扫了一遍，数据水，可以过。

坑点：开始提交过不去，G++ 输出double 要用%f, c++可以使用%lf，一般大佬是不会遇到这种zz问题的。。。

附上ac代码

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#define maxn 100005
#define INF 1<<30
using namespace std;
typedef long long ll;
struct node
{
     double x, y;
     int flag;                //flag用来标记点初始时属于哪个部分
};
node a[maxn * 2];
node p[maxn], q[maxn];
bool cmp(node a, node b){
     return a.x < b.x;
}
double dis(node a, node b){
     if(a.flag != b.flag)     //两个点不属于同一部分再计算
          return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
     else                     //两个点属于同一部分的直接赋值无穷大
          return INF;
}
double solve(int l, int r){
     if(l == r)               //同一个点的距离为无穷大
          return INF;
     if(l == r - 1)           //两个相邻的点是子问题的递归终点
          return dis(a[l], a[r]);
     int mid = (l + r) >> 1;
     double tmp1 = solve(l, mid);
     double tmp2 = solve(mid + 1, r);
     double mi = min(tmp1, tmp2);
     printf("mi = %lf\n", mi);
     int t1 = 0, t2 = 0;
     for(int i = mid; i >= l; i--){     //左一半中的距离可能最小的点
          if((a[mid].x - a[i].x) < mi)
               p[t1++] = a[i];
     }
     for(int i = mid + 1; i <= r; i++){ //右一半中的距离可能最小的点
          if((a[i].x - a[mid].x) < mi)
               q[t2++] = a[i];
     }
     for(int i = 0; i < t1; i++){       //这里直接暴力扫了两个数组，其实只用考虑六个点即可
          for(int j = 0; j < t2; j++)
               mi = min(mi, dis(p[i], q[j]));
     }
     return mi;
}
int main(){
     int T;
     scanf("%d", &T);
     while(T--){
          int n;
          scanf("%d", &n);
          for(int i = 0; i < n; i++){
               scanf("%lf%lf", &a[i].x, &a[i].y);
               a[i].flag = 1; //在输入的时候将两部分点放到一个数组，但用flag标记一下
          }
          for(int i = n; i < 2 * n; i++){
               scanf("%lf%lf", &a[i].x, &a[i].y);
               a[i].flag = 2;
          }
          n = n << 1;
          sort(a, a + n, cmp);//将所有的点放在一起，按照x排序
          printf("%.3f\n",solve(0, n-1));
     }
     return 0;
}