【前言】话说好久没有写题解了。到暑假了反而忙。o(?□?)o

【原题】

Description

Xaviera现在遇到了一个有趣的问题。
平面上有N个点，Xaviera想找出周长最小的三角形。
由于点非常多，分布也非常乱，所以Xaviera想请你来解决这个问题。
为了减小问题的难度，这里的三角形也包括共线的三点。

Input

第一行包含一个整数N表示点的个数。
接下来N行每行有两个整数，表示这个点的坐标。

Output

输出只有一行，包含一个6位小数，为周长最短的三角形的周长（四舍五入）。

Sample Input

Sample Output

HINT

100%的数据中N≤200000。

Source

Day1

【分析】今天新学了解决这类问题的方法――分治。没错，就是分治。

先讲一下n是10^5级别的平面最近点对吧（CF 245 DIV 2 D）。很容易懂。

详细的原理可以参考这个博客，讲的很详细。（很多时候只要感性认识原理即可）下面讲一下具体做法。

①对于平面上的点，按x坐标排序（这是永久排序）。

②每次递归（l，r），函数的返回值是第l个到第r个之间的所有点的最近点对。

③如果l=r，那么返回无穷大；如果l+1=r，就直接返回两个点的距离。

④每次先递归（l，mid）和（mid+1，r）。显然，这两个会有两个返回值，不妨设为d1和d2。首先我们设D=MIN(d1,d2)，即当前的最优值暂时是D。

⑤显然，还有一种情况。左边那块的某个点和右边那块的某个点产生关系。那么，我们可以从mid这个位置向左跑到mid-D，向右跑到mid+D，然后把这一段中的点都拎出来――因为只有这两段中的点才有可能产生小于D的贡献。

⑥这时候我们要意识到潜在复杂度的保证（实际原理也不难懂呵）。首先，如果直接枚举两两点要N^2。我们先把拎出来的点按y排序。（NlogN）然后看似也是N^2的枚举，只是加了一个优化（从底下开始枚举i，如果Y[J]-Y[I]>D就直接break）――这样可证明几乎是线性。总复杂度N*logN*logN。

再讲一下本题，也是差不多道理。因为是三角形，我们把一些细节改一下即可。

【代码】

#include
  
   
#include
   
     #include
    
      #define N 200005 #define INF 210000000000.0 using namespace std; struct arr{int x,y;}a[N],num[N];int n,i,Test; inline bool cmpx(const arr &a,const arr &b){return a.x
     
      >1; double d1=work(l,mid),d2=work(mid+1,r); double D=min(d1,d2),ans=D,DD=D/2.0;int cnt=0; for (int i=l;i<=r;i++) if (fabs(a[mid].x-a[i].x)<=DD) num[++cnt]=a[i]; sort(num+1,num+cnt+1,cmpy); for (int i=1;i
      
       DD) break; for (int k=j+1;k<=cnt;k++) { if (num[k].y-num[i].y>DD) break; double temp=dis(num[i],num[j])+dis(num[i],num[k])+dis(num[j],num[k]); if (temp