凸多边形以及凹多边形的区别：
点集的凸包
定义：在平面上能包含所有给定点的最小凸多边形叫做凸包。
形象理解：礼品包裹法
性质：是包含所有的点的多边形中周长最小的
礼品包裹法
时间复杂度：(O(nh ))，n为所有的点，h为凸包上的点。
这种算法只是玩一玩。
思路：找边界的一个点（最左边，如果有多个是相同的，那么就取最下面）
然后过这一个点做射线逆时针旋转，找到第一个碰到的点，这一个点也加入凸包中
这里不太想实现，太low了。
Graham 扫描算法
题目描述
农夫约翰想要建造一个围栏用来围住他的奶牛，可是他资金匮乏。他建造的围栏必须包括他的奶牛喜欢吃草的所有地点。对于给出的这些地点的坐标，计算最短的能够围住这些点的围栏的长度。
输入格式
输入数据的第一行是一个整数。表示农夫约翰想要围住的放牧点的数目 (n)。
第 (2) 到第 ((n + 1)) 行，每行两个实数，第 ((i + 1)) 行的实数 (x_i, y_i) 分别代表第 (i) 个放牧点的横纵坐标。
输出格式
输出输出一行一个四舍五入保留两位小数的实数，代表围栏的长度。
4
4 8
4 12
5 9.3
7 8
12.00
数据规模与约定：
对于 (100\%) 的数据，保证 (1 \leq n \leq 10^5)，(-10^6 \leq x_i, y_i \leq 10^6)。小数点后最多有 (2) 位数字。
废话不说，直接上代码：
鉴于原题是毒瘤题，所以除了前两个可以过就行了
#include
using namespace std;
#define N 100020
class Point{
public:
double x, y;
Point(){};
Point(double x1, double y1){
x = x1;
y = y1;
}
void disp(){
printf("(%g, %g)", x, y);
}
};
int n;
Point a[N];
Point stac[N];
int top = 0;
Point operator -(const Point &p1, const Point &p2){
return Point(p1.x - p2.x, p1.y - p2.y);
}
double Det(const Point &p1, const Point &p2){
return p1.x*p2.y-p1.y*p2.x;
}
int Direction(const Point &p0, const Point &p1, const Point &p2)
{
double d = Det(p1-p0, p2-p0);
if(d > 0) return 1;
else if(d == 0) return 0;
else return -1;
}
bool cmp(const Point &p1, const Point &p2)
{
return Direction(a[1], p1, p2) > 0;
}
double Distance(const Point &p1, const Point &p2)
{
Point t = p1-p2;
return sqrt(t.x*t.x + t.y*t.y);
}
void solve()
{
int pos = -1;
for(int i = 1; i = 2 && ( Direction(stac[top-1], stac[top], a[i]) < 0 ||
Direction(stac[top-1], stac[top], a[i]) == 0 &&
Distance(stac[top-1], a[i]) > Distance(stac[top-1], stac[top]))
)
{
top --;
}
stac[++top] = a[i];
}
}
int main()
{
scanf("%d", &n);
for(int i = 1; i
这一个算法的时间复杂度是(nlogn)（排序的时间）
Andrew 算法求凸包
这一个算法的时间复杂度是(nlogn)（瓶颈也在排序的时间）
Original: https://www.cnblogs.com/xjsc01/p/16684272.html
Author: 心坚石穿
Title: 【算法设计与分析 李春葆】计算几何（二）——求解凸包问题
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/604110/
转载文章受原作者版权保护。转载请注明原作者出处！