0729-平面分治-BZOJ2458
激动ing，本蒟蒻第一次自己写出一道平面分治的题~~值得纪念
悲伤ing，一开始在一个伪OJ上交，最后一个点一直WA，然后我就改啊改啊改，最后还是WA
于是我无奈之下去找题解，交上去居然也WA（我还找了两篇）
然后啊然后我就跑去BZOJ上交，然后就AC了。。。。。。
这是一个悲伤的故事……
2458: [BeiJing2011]最小三角形
Description
Xaviera现在遇到了一个有趣的问题。
平面上有N个点，Xaviera想找出周长最小的三角形。
由于点非常多，分布也非常乱，所以Xaviera想请你来解决这个问题。
为了减小问题的难度，这里的三角形也包括共线的三点。
Input
第一行包含一个整数N表示点的个数。
接下来N行每行有两个整数，表示这个点的坐标。
Output
输出只有一行，包含一个6位小数，为周长最短的三角形的周长（四舍五入）。
Sample Input
4
1 1
2 3
3 3
3 4
Sample Output
3.414214
HINT
100%的数据中N≤200000。
分析
我看网上有人说这是一道计算几何的题，可是蒟蒻表示计算几何没学好，并没有看出来
不过分治倒是很好做，和平面上的最近点对简直一模一样，只需要稍作修改即可
具体做法如下：
①对于平面上的点，按x坐标排序（这是永久排序）。
②每次递归处理左右区间（l，mid）和（mid + 1 ，r ），函数的返回值是第l个到第r个之间的最小的三角形的周长。
③如果l+1==r，那么返回无穷大（说明现在只有两个点，是构不成三角形的）；如果l+2=r，就直接返回三个点，两两搭配的距离。
④而每次先递归（l，mid）和（mid+1，r）。显然，这两个会有两个返回值，不妨设为d1和d2。首先我们设D=MIN(d1,d2)，即当前的最优值暂时是D。
⑤显然，还有一种情况。左边那块的某些点和右边那块的某些点产生关系。那么，我们可以从mid这个位置向左跑到mid-D/2，向右跑到mid+D/2，然后把这一段中的点都拎出来——因为只有这两段中的点才有可能产生小于D的贡献。然后再在这些点中，按 y坐标排序，三层循环大暴力就好啦（记得适当剪枝即可）
（至于为什么要D/2，就是因为如果两个点之间的距离比d/2还大，那么根据三角形定理，剩下两边之和一定大于d/2，则三边之和大于d，不会产生更优的解）
代码
（写的不优秀，但至少自己想的，请海涵）
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 200009
#define inf 0x3f3f3f3f3f
using namespace std;
int n,a[N];
struct node{
double x,y;
}p[N];
bool cmpx(const node &a,const node &b){
return a.x<b.x;
}
bool cmpy(int a,int b){
return p[a].y<p[b].y;
}
double dis(const node &a,const node &b){
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double solve(int l,int r){
if(l+1==r) return inf;
if(l+2==r) return dis(p[l],p[l+1])+dis(p[l],p[r])+dis(p[l+1],p[r]);
int mid=l+r>>1,t=0;
double d=min(solve(l,mid),solve(mid+1,r));
double dd=d/2.0;
int i,j,k;
for(i=l;i<=r;++i)
if(dd-fabs(p[i].x-p[mid].x)>1e-10)
a[++t]=i;
sort(a+1,a+t+1,cmpy);
for(i=1;i<=t;++i)
{
for(j=i+1;j<=t;++j)
{
if(fabs(p[a[i]].x-p[a[j]].x)-dd>1e-8) continue;
if(p[a[j]].y-p[a[i]].y-dd>1e-8) break;
for(k=j+1;k<=t;++k){
if(fabs(p[a[i]].x-p[a[k]].x)-dd>1e-8) continue;
if(p[a[k]].y-p[a[i]].y-dd>1e-8) break;
if(fabs(p[a[k]].x-p[a[j]].x)-dd>1e-8) continue;
if(p[a[k]].y-p[a[j]].y-dd>1e-8) break;
d=min(d,dis(p[a[i]],p[a[j]])+dis(p[a[i]],p[a[k]])+dis(p[a[k]],p[a[j]]));
dd=d/2.0;
}
}
}
return d;
}
int main(){
scanf("%d",&n);
int i,j,k;
for(i=1;i<=n;++i)
scanf("%lf%lf",&p[i].x,&p[i].y);
sort(p+1,p+n+1,cmpx);
printf("%.6lf",solve(1,n));
return 0;
}