算法三十二：凸包

比眉伴天荒 2022-05-21 09:11 245阅读 0赞

### **描述** ###

给定n个二维平面上的点，求他们的凸包。

### **输入** ###

第一行包含一个正整数n。

接下来n行，每行包含两个整数x,y，表示一个点的坐标。

### **输出** ###

令所有在凸包极边上的点依次为p1,p2,...,pm（序号），其中m表示点的个数，请输出以下整数：

(p1 × p2 × ... × pm × m) mod (n + 1)

### **样例输入** ###

10
    7 9
    -8 -1
    -3 -1
    1 4
    -3 9
    6 -4
    7 5
    6 6
    -6 10
    0 8

### **样例输出** ###

### **样例解释** ###

![cb9dbfbef90751cc0bc372041f543118dc6c9f1a.png][]

所以答案为(9 × 2 × 6 × 7 × 1 × 5) % (10 + 1) = 7

### **一. 伪代码** ###

![70][]

### **二. 具体实现** ###

\#include <bits/stdc++.h>  
using namespace std;  
// ================= 代码实现开始 =================  
typedef long long ll;  
const int N = 300005;  
// 存储二维平面点  
struct ip \{  
int x, y, i;  
ip(int x = 0, int y = 0) : x(x), y(y), i(0) \{ \}  
void ri(int \_i) \{  
scanf("%d%d", &x, &y);  
i = \_i;  
\}  
\};  
// iv表示一个向量类型，其存储方式和ip一样  
typedef ip iv;  
// 先比较x轴再比较y轴，  
bool operator < (const ip &a, const ip &b) \{  
return a.x == b.x ? a.y < b.y : a.x < b.x;  
\}  
// 两点相减得到的向量  
iv operator - (const ip &a, const ip &b) \{  
return iv(a.x - b.x, a.y - b.y);  
\}  
// 计算a和b的叉积（外积）  
ll operator ^ (const iv &a, const iv &b) \{  
return (ll)a.x \* b.y - (ll)a.y \* b.x;  
\}  
// 计算二维点数组a的凸包，将凸包放入b数组中，下标均从0开始  
// a, b：如上  
// n：表示a中元素个数  
// 返回凸包元素个数  
int convex(ip \*a, ip \*b, int n) \{  
 //升序排序  
sort(a,a+n);  
int m = 0;  
 //求下凸壳  
for(int i = 0; i < n; ++i)\{  
for(; m > 1 && ((b\[m-1\] - b\[m-2\])^(a\[i\] - b\[m-2\])) < 0; --m);  
b\[m++\] = a\[i\];  
\}  
 //求上凸壳  
for(int i = n - 2, t = m; i >= 0; --i)\{  
for(; m > t && ((b\[m-1\] - b\[m-2\])^(a\[i\] - b\[m-2\])) < 0; --m);  
b\[m++\] = a\[i\];  
\}  
return m - 1;  
\}  
// ================= 代码实现结束 =================

[cb9dbfbef90751cc0bc372041f543118dc6c9f1a.png]: /images/20220521/f804b471816c4954bc250523085db177.png
[70]: /images/20220521/ec5ad0f97c4a4e56b03a3d39cd7742b6.png