BZOJ 2458 BeiJing 2011 最小三角形 分治

BZOJ 2458 BeiJing 2011 最小三角形 分治

題目大意：給出平面上一些點，問這些點組成的最小周長三角形的周長是多少。

思路：與平面最近點對類似的思想，先按照x值排序，通過全局目前搜到的最優解來縮小分治之後需要暴力枚舉的范圍。具體來說，遞歸的終止條件是需要處理的點數小於一定數量，就在這些點中暴力枚舉來更新答案。這個值經過測定，在這個題中20左右為最快的。具體怎麼算我也不知道。。

之後每處理一段區間，先遞歸處理左右區間來更新答案，弄出一個中軸來，設目前為止最優的答案是c，那麼只保留距離中軸距離不超過c / 2的點來處理，不難證明在這之外的點不可能更新答案。
這些點中暴力枚舉還是太多了，還需要一個小優化。對於左邊的每個點來說，能夠與這個點組成三角形的右邊的兩個點也是有限的。具體來說，y值相差超過c / 2的點是肯定不能與它組成三角形來更新答案的。這個在紙上畫一畫很顯然就能夠得到答案。

PS：寫分治的時候要分清‘1’和‘l’啊。。

CODE：

#include 
#include 
#include 
#include 
#include 
#include 
#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;
}