首页 > 代码库 > [bzoj1670][Usaco2006 Oct]Building the Moat
[bzoj1670][Usaco2006 Oct]Building the Moat
Description
为了防止口渴的食蚁兽进入他的农场，$Farmer John$决定在他的农场周围挖一条护城河。农场里一共有$N$股泉水，并且，护城河总是笔直地连接在河道上的相邻的两股泉水。护城河必须能保护所有的泉水，也就是说，能包围所有的泉水。泉水一定在护城河的内部，或者恰好在河道上。当然，护城河构成一个封闭的环。 挖护城河是一项昂贵的工程，于是，节约的$FJ$希望护城河的总长度尽量小。请你写个程序计算一下，在满足需求的条件下，护城河的总长最小是多少。
所有泉水的坐标都在范围为$(1..10^7,1..10^7)$的整点上，一股泉水对应着一个唯一确定的坐标。并且，任意三股泉水都不在一条直线上。
以下是一幅包含$20$股泉水的地图，泉水用$"*"$表示。
图中的直线，为护城河的最优挖掘方案，即能围住所有泉水的最短路线。
路线从左上角起，经过泉水的坐标依次是：$(18,0)$,$(6,-6)$,$(0,-5)$,$(-3,-3)$,$(-17,0)$,$(-7,7)$,$(0,4)$,$(3,3)$。绕行一周的路径总长为$70.8700576850888...$。答案只需要保留两位小数，于是输出是$70.87$。
Input
第$1$行:一个整数$N$。
第$2..N+1$行:每行包含$2$个用空格隔开的整数，$x[i],y[i]$，即第$i$股泉水的位置坐标。
Output
一行一个数字，表示满足条件的护城河的最短长度。保留两位小数。
Sample Input
20
2 10
3 7
22 15
12 11
20 3
28 9
1 12
9 3
14 14
25 6
8 1
25 1
28 4
24 12
4 15
13 5
26 5
21 11
24 4
1 8
Sample Output
70.87
HINT
$8\;\leq\;N\;\leq\;5000$.
Solution
求凸包周长.
#include<set> #include<cmath>#include<ctime>#include<queue>#include<stack>#include<cstdio>#include<vector>#include<cstring>#include<cstdlib>#include<iostream>#include<algorithm>#define N 5005#define eps 1e-11using namespace std;struct point{ int x,y;double t;}a[N],v[N];int n,u,vn;inline double sqr(int k){ return (double)(k*k);}inline point dec(point x,point y){ return (point){x.x-y.x,x.y-y.y,0.0};}inline int mult(point x,point y){ return x.x*y.y-y.x*x.y;}inline double dis(point x,point y){ return sqrt(sqr(abs(x.x-y.x))+sqr(abs(x.y-y.y)));}inline bool cmp(point x,point y){ if(fabs(x.t-y.t)<eps) return dis(x,a[1])>dis(y,a[1]); return x.t<y.t;} inline void convex(){ u=1; for(int i=2;i<=n;i++) if((a[i].x<a[u].x)||(a[i].x==a[u].x&&a[i].y<a[u].y)) u=i; a[0]=a[u];a[u]=a[1];a[1]=a[0]; for(int i=2;i<=n;i++) a[i].t=atan2(a[i].y-a[1].y,a[i].x-a[1].x); sort(a+2,a+1+n,cmp); v[++vn]=a[1];v[++vn]=a[2];a[++n]=a[1]; for(int i=3;i<=n;i++){ if(fabs(a[i].t-a[i-1].t)<eps) continue; while(vn>1&&mult(dec(a[i],v[vn-1]),dec(v[vn],v[vn-1]))>0) vn--; v[++vn]=a[i]; }}inline double cir(){ double ret=0; for(int i=2;i<=vn;i++) ret+=dis(v[i],v[i-1]); return ret;} inline void init(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y); convex(); printf("%.2lf\n",cir()); }int main(){ freopen("convex.in","r",stdin); freopen("convex.out","w",stdout); init(); fclose(stdin); fclose(stdout); return 0;}
[bzoj1670][Usaco2006 Oct]Building the Moat