【学习笔记】凸包

原题传送门
因为做到一道题学了Andrew算法和Graham算法
Andrew算法莫名咕
脑子有点混，所以具体部分先鸽着（我竟然也会鸽了）

主要是先按照极角排序，然后搞一搞……

Code：

#include <bits/stdc++.h>
#define maxn 10010
using namespace std;
int n;

struct Point{
	double x, y;
	void read(){ scanf("%lf%lf", &x, &y); }
	Point operator - (const Point &a) const{ return (Point) { x - a.x, y - a.y}; }
	double operator * (const Point &a) const{ return x * a.y - y * a.x; }
}p[maxn], GP;

double cross(Point x, Point y, Point z){ return (y - x) * (z - x); }

double dis(Point a, Point b){
	return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

bool cmp(Point x, Point y){
	double tmp = cross(GP, x, y);
	return tmp != 0 ? tmp > 0 : dis(x, GP) < dis(y, GP);
}

int main(){
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) p[i].read();
	GP = p[1];
	for (int i = 2; i <= n; ++i)
		if (p[i].y < GP.y || (p[i].y == GP.y && p[i].x < GP.x)) GP = p[i];
	sort(p + 1, p + 1 + n, cmp);
	int top = 2;
	for (int i = 3; i <= n; ++i){
		while (top >= 2 && cross(p[top - 1], p[top], p[i]) <= 0) --top;
		p[++top] = p[i];
	}
	double ans = 0;
	for (int i = 1; i < top; ++i) ans += dis(p[i], p[i + 1]);
	printf("%.2lf\n", ans + dis(p[1], p[top]));
	return 0;
}