[BZOJ]2458: [BeiJing2011]最小三角形

题目大意：给出平面上n个点，求最小的由这些点组成的三角形的周长。（N<=200,000）

思路：点按x坐标排序后分治，每次取出与排在中间的点的横坐标相差不超当前答案一半的点，按y坐标排序后再暴力枚举y坐标相差不超过当前答案一半的三个点统计答案，复杂度O(能过)（听说期望nlogn）。

#include<cstdio>

#include<cmath>

#include<algorithm>

using namespace std;

inline int read()

{

    int x,f=;char c;

    while((c=getchar())<''||c>'')if(c=='-')f=-;

    for(x=c-'';(c=getchar())>=''&&c<='';)x=(x<<)+(x<<)+c-'';

    return x*f;

}

#define MN 200000

double ans=1e18;

struct P{int x,y;}p[MN+],t[MN+];

bool cmpx(P a,P b){return a.x<b.x;}

bool cmpy(P a,P b){return a.y<b.y;}

double sqr(double x){return x*x;}

double len(P a,P b){return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));}

void solve(int l,int r)

{

    if(r-l<)return;

    int m=l+r>>,i,j,k,cnt=;

    solve(l,m);solve(m+,r);

    for(i=l;i<=r;++i)if(fabs(p[i].x-p[m].x)<ans/)t[++cnt]=p[i];

    sort(t+,t+cnt+,cmpy);

    for(i=;i<=cnt;++i)for(j=i+;j<=cnt&&t[j].y-t[i].y<ans/;++j)for(k=j+;k<=cnt&&t[k].y-t[i].y<ans/;++k)

        ans=min(ans,len(t[i],t[j])+len(t[j],t[k])+len(t[k],t[i]));

}

int main()

{

    int n=read(),i;

    for(i=;i<=n;++i)p[i].x=read(),p[i].y=read();

    sort(p+,p+n+,cmpx);

    solve(,n);

    printf("%.6lf",ans);

}

秒客网

[BZOJ]2458: [BeiJing2011]最小三角形

相关文章