BZOJ 2458 BeiJing 2011 최소 삼각형 분할

제목 대의: 평면상의 몇 가지 점을 제시하고 이 점들로 구성된 최소 둘레 삼각형의 둘레가 얼마나 되는지 물어본다.
사고방식: 평면 최근점과 유사한 사상은 먼저 x값에 따라 순서를 정하고 전체 국면에서 현재 검색된 가장 좋은 해석을 통해 분리된 후에 폭력적인 매거진의 범위를 좁힌다.구체적으로 말하면 귀속의 종지 조건은 처리해야 할 포인트가 일정한 수량보다 적고 이 점에서 폭력적인 매거진을 통해 답을 갱신하는 것이다.이 값은 측정을 거쳐 이 문제에서 20 정도가 가장 빠르다.구체적으로 어떻게 쳐도 모르겠어요.
이후에 한 구간을 처리할 때마다 먼저 좌우 구간을 차례로 처리하여 답안을 갱신하고 중축을 만들어낸다. 지금까지 가장 좋은 답안은 c이다. 그러면 중축 거리가 c/2를 넘지 않는 점만 보류하여 처리하면 이 이외의 점에서 답안을 갱신할 수 없다는 것을 증명하기 어렵지 않다.이 점들 중에는 폭력적인 매거진이 너무 많아서 작은 최적화가 필요하다.왼쪽의 각 점에 대해 말하자면, 이 점과 삼각형을 구성할 수 있는 오른쪽의 두 점도 유한하다.구체적으로 말하면 y치의 차이가 c/2를 초과하는 점은 그것과 삼각형을 이루어 답을 갱신할 수 없을 것이다.이것은 종이 위에 그림을 그리면 분명히 답을 얻을 수 있다.
PS: 분치를 쓸 때'1'과'l'를 구분해야 하는데...
CODE:

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#define MAX 200010
#define INF 1e15
using namespace std;
  
struct Point{
    double x,y;
  
    bool operator <(const Point &a)const {
        return x < a.x;
    }
    void Read() {
        scanf("%lf%lf",&x,&y);
    }
}point[MAX],L[MAX],R[MAX];
  
inline bool cmp(const Point &p1,const Point &p2)
{
    return p1.y < p2.y;
}
  
inline double Calc(const Point &p1,const Point &p2)
{
    return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}
  
int points;
 
double re = INF;
  
void Solve(int l,int r)
{
    if(r - l <= 20) {
        for(int i = l; i <= r; ++i)
            for(int j = i + 1; j <= r; ++j)
                for(int k = j + 1; k <= r; ++k)
                    re = min(re,Calc(point[i],point[j]) + Calc(point[j],point[k]) + Calc(point[k],point[i]));
        return ;
    }
    int mid = (l + r) >> 1; 
    Solve(l,mid),Solve(mid + 1,r);
    double x = (point[mid].x + point[mid + 1].x) / 2;
    int ltop = 0,rtop = 0;
    for(int i = mid; x - point[i].x < re / 2 && i; --i)              L[++ltop] = point[i];
    for(int i = mid + 1; point[i].x - x < re / 2 && i <= r; ++i)  R[++rtop] = point[i];
    sort(L + 1,L + ltop + 1,cmp);
    sort(R + 1,R + rtop + 1,cmp);
    int down = 1,up = 1;
    for(int i = 1; i <= ltop; ++i) {
        while(L[i].y - R[down].y > re / 2 && down < rtop) ++down;
        while(R[up].y - L[i].y < re / 2 && up < rtop)     ++up;
        for(int j = down; j <= up; ++j)
            for(int k = j + 1; k <= up; ++k)
                re = min(re,Calc(L[i],R[j]) + Calc(L[i],R[k]) + Calc(R[j],R[k]));
    }
    down = up = 1;
    for(int i = 1; i <= rtop; ++i) {
        while(R[i].y - L[down].y > re / 2 && down < ltop) ++down;
        while(L[up].y - R[i].y < re / 2 && up < ltop)     ++up;
        for(int j = down; j <= up; ++j)
            for(int k = j + 1; k <= up; ++k)
                re = min(re,Calc(R[i],L[j]) + Calc(R[i],L[k]) + Calc(L[j],L[k]));
    }
}
  
int main()
{
    cin >> points;
    for(int i = 1; i <= points; ++i)
        point[i].Read();
    sort(point + 1,point + points + 1);
    Solve(1,points);
    cout << fixed << setprecision(6) << re << endl;
    return 0;
}