Smiling & Weeping

　　　　　　　　　　　　　　　　----秋天把旧叶子揉掉了，你要听新故事吗。

　　　　　　　　　　　　　　　　　　　　　　静静的河水睁着眼睛，

　　　　　　　　　　　　　　　　　　笑着说：总要有回家的人，总有离岸的船。

题目链接：P2742 [USACO5.1] 圈奶牛Fencing the Cows /【模板】二维凸包 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路：(• •)阿巴阿巴~

Talk is cheap , show me the code

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N = 1e5+1;
 4 const double eps = 1e-6;
 5 int sgn(double x){
 6     if(fabs(x) < eps) return 0;
 7     else return x<0 ? -1 : 1;
 8 }
 9 struct Point{
10     double x,y;
11     Point(){}
12     Point(double x , double y): x(x),y(y){}
13     Point operator + (Point b) { return Point(x+b.x , y+b.y); }
14     Point operator - (Point b) { return Point(x-b.x , y-b.y); }
15     bool operator == (Point b) { return sgn(x-b.x)==0 && sgn(y-b.y)==0; }
16     bool operator < (Point b){
17         return sgn(x-b.x)<0 || (sgn(x-b.x)==0 && sgn(y-b.y)<0);
18     }
19 };
20 typedef Point Vector;
21 double Cross(Vector a , Vector b){
22     return a.x*b.y - a.y*b.x;
23 }
24 double Distance(Point a, Point b){return hypot(a.x-b.x , a.y-b.y); }
25 int Convex_hull(Point *p,int n , Point *ch){
26     n = unique(p,p+n)-p;
27     sort(p , p+n);
28     int v = 0;
29     for(int i = 0; i < n; i++){
30         while(v > 1 && sgn(Cross(ch[v-1]-ch[v-2] , p[i]-ch[v-1]))<=0)
31             v--;
32         ch[v++] = p[i];
33     }
34     int j = v;
35     for(int i = n-2; i >= 0; i--){
36         while(v > j && sgn(Cross(ch[v-1]-ch[v-2] , p[i]-ch[v-1]))<=0)
37             v--;
38         ch[v++] = p[i];
39     }
40     if(n>1) v--; // 因为最后一个一定要首尾相接，但是第一个一定保存了，所以个数减一
41     return v;
42 }
43 Point p[N] , ch[N];
44 int main()
45 {
46     int n;
47     scanf("%d",&n);
48     for(int i = 0; i < n; i++)
49         scanf("%lf %lf",&p[i].x,&p[i].y);
50     int v = Convex_hull(p , n , ch);
51     double ans = 0;
52     for(int i = 0; i < v; i++)
53         ans += Distance(ch[i],ch[(i+1)%v]);
54     printf("%.2f\n",ans);
55     return 0;
56 }

你所在之处，是我不得不思念的海角天涯

文章到此结束，我们下次再见ヾ(￣▽￣)Bye~Bye~