[BZOJ2458][BeiJing2011]最小三角形

題目描述?Description

Xaviera現在遇到了一個有趣的問題。平面上有N個點，Xaviera想找出周長最小的三角形。由于點非常多，分布也非常亂，所以Xaviera想請你來解決這個問題。為了減小問題的難度，這里的三角形也包括共線的三點。

輸入描述?Input Description

第一行包含一個整數N表示點的個數。接下來N行每行有兩個整數，表示這個點的坐標。

輸出描述?Output Description

輸出只有一行，包含一個6位小數，為周長最短的三角形的周長（四舍五入）。

樣例輸入 Sample Input

4

1 1

2 3

3 3

3 4

樣例輸出 Sample Output

3.414214

數據范圍及提示 Data Size & Hint

?

之前的一些廢話：是時候準備會考了。。

題解：做法類似平面上求最近點對。首先把平面劃分成兩個部分，遞歸求出兩個部分的答案為ans，然后，把離分割線距離小于ans/2的點全部加入隊列，因為只有在這范圍內答案才有可能比ans小，加入之后按照y坐標排一遍序，然后滑動窗口維護一下高度為ans/2的一個矩形，然后對矩形內的點暴力選，更新最優解即可。

代碼：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
#define mem(a,b) memset(a,b,sizeof(a))
typedef pair<double,int> PDI;
const int maxn=200010;
const double oo=2147483647;
inline int read()
{int x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}return x*f;
}
struct Point
{double x,y;Point() {}Point(double _1,double _2):x(_1),y(_2){}bool operator < (const Point &s)const{if(x==s.x)return y<s.y;return x<s.x;}
}p[maxn];
int n;double x,y;
PDI s[maxn];
double dis(double a,double b,double c,double d){return sqrt((c-a)*(c-a)+(d-b)*(d-b));
}
double triangle_perimeter(double a,double b,double c,double d,double e,double f){return dis(a,b,c,d)+dis(a,b,e,f)+dis(c,d,e,f);
}
bool cmp(PDI a,PDI b){return a.first<b.first;} 
double mdis(int l,int r)
{if(l+1>=r)return oo;if(l+2==r)return triangle_perimeter(p[l].x,p[l].y,p[l+1].x,p[l+1].y,p[r].x,p[r].y);int mid=(l+r)>>1,t=0;double d=min(mdis(l,mid),mdis(mid,r));for(int i=l;i<=r;i++)if(fabs(p[i].x-p[mid].x)<=d/2.0)s[t++]=make_pair(p[i].y,i); sort(s,s+t,cmp);int st=0,ed;while(st<=t-2){ed=st+1;while(fabs(s[ed].first-s[st].first)<=(d/2.0) && ed<=t-2)ed++;for(int i=st+1;i<ed;i++)for(int j=i+1;j<ed;j++)d=min(d,triangle_perimeter(p[s[st].second].x,p[s[st].second].y,p[s[i].second].x,p[s[i].second].y,p[s[j].second].x,p[s[j].second].y)); st++;}return d;
}
int main()
{n=read();for(int i=0;i<n;i++)x=(double)read(),y=(double)read(),p[i]=Point(x,y);sort(p,p+n);printf("%.6lf\n",mdis(0,n-1));return 0;
}

總結：滑動窗口好難寫。