凸包

1. Luogu P2742 [USACO5.1]圈奶牛Fencing the Cows /【模板】二维凸包

上面是板子题

Andrew 算法

1. 对所有点按坐标 x 为第一关键字、 y 为第二关键字排序。第1、第n两个点一定在凸包上。
2. 先顺序枚举所有点，求下凸包。用栈维护当前在凸包上的点：新点入栈前，总要判断该弹出哪些旧点。只要新点处在由栈顶两点构成的有向直线的右侧或共线，就弹出旧点。不能弹出时，新点入栈。
3. 再逆序枚举所有点，求上凸包。用栈维护同上。

注意：每个点入栈两次，出栈不超过两次，所以总次数不超过 。

注意：最后封口时，栈底和栈顶存的都是第一个点。

时间：O(nlogn）

 1 #include <iostream>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <cmath>
 5 using namespace std;
 6 
 7 const int N=100010;
 8 struct Point{double x,y;} p[N],s[N];
 9 int n,top;
10 
11 double cross(Point a,Point b,Point c){ //叉积
12   return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
13 }
14 double dis(Point a,Point b){ //距离
15   return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
16 }
17 bool cmp(Point a, Point b){ //比较
18   return a.x!=b.x ? a.x<b.x : a.y<b.y;
19 }
20 double Andrew(){
21   sort(p+1,p+n+1,cmp); //排序
22   for(int i=1; i<=n; i++){ //下凸包
23     while(top>1&&cross(s[top-1],s[top],p[i])<=0)top--;
24     s[++top]=p[i];
25   }
26   int t=top;
27   for(int i=n-1; i>=1; i--){ //上凸包
28     while(top>t&&cross(s[top-1],s[top],p[i])<=0)top--;
29     s[++top]=p[i];
30   }
31   double res=0; //周长
32   for(int i=1; i<top; i++) res+=dis(s[i],s[i+1]);
33   return res;
34 }
35 int main(){
36   scanf("%d",&n);
37   for(int i=1;i<=n;i++)scanf("%lf%lf",&p[i].x,&p[i].y);
38   printf("%.2lf\n", Andrew());
39   return 0;
40 }

2. Luogu P3829 [SHOI2012]信用卡凸包

思路：圆弧之和=圆的周长

　　　直边之和=所有圆心构成的凸包的周长

时间：O(nlogn)

 1 #include <bits/stdc++.h>  //
 2 using namespace std;
 3 #define endl '\n'
 4 int _,k, m;
 5 
 6 const double pi = acos(-1);
 7 
 8 
 9 typedef pair<double, double> point;
10 point p[N], s[N];
11 int n, top, cnt;
12 
13 point operator-(point a,point b){ //向量-
14   return point(a.x-b.x,a.y-b.y);
15 }
16 
17 double dis(point a, point b) {  //距离
18   return sqrt((b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y));
19 }
20 
21 double cross(point a, point b, point c) {  //叉积
22   return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
23 }
24 
25 //逆转角
26 point rotate(point a, double b) {  //将某个向量逆时针旋转b°
27   return point(a.x * cos(b) - a.y * sin(b), a.x * sin(b) + a.y * cos(b));
28 }
29 
30 bool cmp(point a, point b) { return a.x != b.x ? a.x < b.x : a.y < b.y; }
31 
32 double Andrew() {
33   sort(p + 1, p + 1 + n);
34   for (int i = 1; i <= n; i++) {  //下凸包
35     //在栈顶和顶下一个元素构成的有向线段的右侧则入栈，左侧弹出上一个入栈的点
36     while (top > 1 && cross(s[top - 1], s[top], p[i]) <= 0) top--;
37     s[++top] = p[i];
38   }
39   int t = top;                        //中间变量存top
40   for (int i = n - 1; i >= 1; i--) {  //上凸包
41     while (top > t && cross(s[top - 1], s[top], p[i]) <= 0) top--;
42     s[++top] = p[i];
43   }
44   double ans = 0;
45   for (int i = 1; i < top; i++) ans += dis(s[i], s[i + 1]);
46   return ans;
47 }
48 
49 void solve() {
50   cin >> n;
51   double a, b, r;
52   cin >> a >> b >> r;
53   a = a / 2 - r, b = b / 2 - r;  //圆心到中心的边距
54   int dx[] = {1, 1, -1, -1}, dy[] = {1, -1, -1, 1};
55   while (n--) {
56     double x, y, z;
57     cin >> x >> y >> z;
58     for (int i = 0; i < 4; i++) {
59       point t = rotate({dx[i] * b, dy[i] * a}, z);  //四个圆心旋转
60       p[++cnt] = {x + t.x, y + t.y};                //中间圆心平移
61     }
62   }
63   n = cnt;  //圆心个数
64   printf("%.2lf\n", Andrew() + 2 * pi * r);
65 }
66 
67 int main() {
68   // cin >> _;
69   _ = 1;
70   while (_--) {
71     solve();
72   }
73   return 0;
74 }

练习：

POJ1113 Wall

思路：答案就是凸包周长 + 半径为 L 的圆的周长

Luogu P4724 【模板】三维凸包

Luogu P2287 [HNOI2004]最佳包裹