cogs896 圈奶牛

描述

农夫约翰想要建造一个围栏用来围住他的奶牛，可是他资金匮乏。他建造的围栏必须包括他的奶牛喜欢吃草的所有地点。对于给出的这些地点的坐标，计算最短的能够围住这些点的围栏的长度。

PROGRAM NAME: fc

INPUT FORMAT(file fc.in)

输入数据的第一行包括一个整数 N。N（0 <= N <= 10,000）表示农夫约翰想要围住的放牧点的数目。接下来 N 行，每行由两个实数组成，Xi 和 Yi,对应平面上的放牧点坐标（-1,000,000 <= Xi,Yi <= 1,000,000）。数字用小数表示。

OUTPUT FORMAT(file fc.out)

输出必须包括一个实数，表示必须的围栏的长度。答案保留两位小数。

SAMPLE INPUT (file fc.in)

SAMPLE OUTPUT (file fc.out)

12.00



graham凸包算法
注意读进来的有小数

 1 /*by SilverN*/
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cmath>
 5 #include<cstring>
 6 #include<algorithm>
 7 #define ll long long
 8 using namespace std;
 9 const int mxn=20000;
10 struct node{
11     double x,y;
12 }p[mxn],s[mxn];
13 int top;
14 double ans;
15 int n;
16 inline node operator -(node a,node b){
17     node T;    T.x=a.x-b.x;    T.y=a.y-b.y;    return T;
18 }
19 inline double operator *(node a,node b){
20     return a.x*b.y-a.y*b.x;
21 }
22 inline double dis(node a,node b){
23     return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
24 }
25 inline bool operator < (node a,node b){
26     ll t=(a-p[1])*(b-p[1]);
27     if(t==0)return dis(a,p[1])<dis(b,p[1]);
28     return t>0;
29 }
30 void graham(){
31     int i,j;
32     int t=1;
33     for(i=2;i<=n;i++){
34         if(p[i].y<p[t].y || (p[i].y==p[t].y && p[i].x<p[t].x))t=i;
35     }
36     swap(p[1],p[t]);
37     sort(p+2,p+n+1);
38     s[1]=p[1];
39     s[2]=p[2];top=2;
40     for(i=3;i<=n;i++){
41         while(top && ((s[top]-s[top-1])*(p[i]-s[top-1]))<0 )top--;
42         s[++top]=p[i];
43     }
44     s[top+1]=p[1];
45     for(i=1;i<=top;i++){
46         ans+=sqrt(dis(s[i],s[i+1]));
47     }
48     return;
49 }
50 int main(){
51 //    freopen("fc.in","r",stdin);
52 //    freopen("fc.out","w",stdout);
53     scanf("%d",&n);
54     int i,j;
55     for(i=1;i<=n;i++){
56         scanf("%lf%lf",&p[i].x,&p[i].y);
57     }
58     graham();
59     printf("%.2lf
",ans);
60     return 0;
61 }

Andrew凸包

 1 /*by SilverN*/
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cstdio>
 6 #include<cmath>
 7 #include<vector>
 8 using namespace std;
 9 const int mxn=100010;
10 struct point{
11     double x,y;
12     point operator + (const point &b){return (point){x+b.x,y+b.y};}
13     point operator - (const point &b){return (point){x-b.x,y-b.y};}
14     point operator * (const double v){return (point){x*v,y*v};}
15     bool operator < (const point &b)const{
16         return x<b.x || (x==b.x && y<b.y);
17     }
18 }a[mxn];
19 double dot(const point &a,const point &b){return a.x*b.x,a.y*b.y;}
20 double Cross(const point &a,const point &b){return a.x*b.y-a.y*b.x;}
21 double dist(const point &a,const point &b){
22     return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
23 }
24 int n;
25 int st[mxn],top,t2;
26 void andrew(){
27     a[n+1]=a[1];
28     top=t2=0;
29     for(int i=1;i<=n;i++){
30         while(top>1 && Cross(a[i]-a[st[top-1]],a[st[top]]-a[st[top-1]])>=0)top--;
31         st[++top]=i;
32     }
33     t2=top;
34     for(int i=n-1;i;i--){
35         while(t2>top && Cross(a[i]-a[st[t2-1]],a[st[t2]]-a[st[t2-1]])>=0)t2--;
36         st[++t2]=i;
37     }
38     return;
39 }
40 int main(){
41 //    freopen("fc.in","r",stdin);
42 //    freopen("fc.out","w",stdout);
43     int i,j;
44     scanf("%d",&n);
45     for(i=1;i<=n;i++)
46         scanf("%lf%lf",&a[i].x,&a[i].y);
47     sort(a+1,a+n+1);
48     andrew();
49 //    for(i=1;i<=t2;i++)
50 //        printf("%.3f %.3f
",a[st[i]].x,a[st[i]].y);
51     double ans=0;
52     for(i=1;i<t2;i++)
53         ans+=dist(a[st[i]],a[st[i+1]]);
54     printf("%.2f
",ans);
55     return 0;
56 }