计算几何

凸包

求凸包可以用 Graham 扫描法。

极角排序后，选一个坐标最小的点作极点，单调栈维护即可。

struct Point {
	int x, y;
	Point() {}
	Point(int x, int y):x(x), y(y) {} 
	friend Point operator - (Point a, Point b) { return Point(a.x - b.x, a.y - b.y); }
	friend int operator ^ (Point a, Point b) { return a.x * b.x + a.y * b.y; }  // dot
	friend int operator * (Point a, Point b) { return a.x * b.y - a.y * b.x); }  // x
	int norm() { return x * x + y * y; }
} p[N], q[N]; 

bool cmp (int a, int b) {
	int det = (p[a] - p[1]) * (p[b] - p[1]);
	if (det != 0) return det > 0;
	return (p[a] - p[1]).norm() < (p[b] - p[1]).norm();
}

int pid[N], top;
void Graham() {
	int id = 1;
	for (int i = 2; i <= n; i++)
		if (p[i].x < p[id].x || (p[i].x == p[id].x && p[i].y < p[id].y)) id = i;
	id (id != 1) swap (p[1], p[id]);
	for (int i = 1; i <= n; i++) pid[i] = i;
	sort (pid + 2, pid + 1 + n, cmp);
	
	q[++top] = p[1];
	for (int i = 2; i <= n; i++) {
		int j = pid[i];
		while (top >= 2 && (p[j] - q[top - 1]) * (q[top] - q[top - 1]) >= 0) top--;
		q[++top] = p[j];
	} 
}

旋转卡壳

对踵点对：如果凸包的顶点 $p,q$ 在两条平行切线，它们就形成了对踵点对。它有三种情况：点点、点边、边边。

以求凸包直径为例感受旋转卡壳。

求凸包直径方法一

一个直观的方法：

1. 找到凸包纵坐标最小和最大两点 $A,B$ ；
2. 构造两条水平切线 $y_1=y_A,y_2=y_B$ ，并先计算其距离更新答案；
3. 同时旋转两条平行线直到其中一条与凸包上一边重合，产生新的点对，更新答案；
4. 重复直到旋转一周。

求凸包直径方法二

以每条边为基础，计算距离最长的点。然后它是有单峰性的，而且上一条边用完可以给这条边接着用。 $\mathcal{O}(n)$

double rotateCalipers (Point *ch, int n) {
	double ans = -INF;
	ch[n + 1] = ch[1];
	int p = 1;
	for (int i = 1; i <= n; i++) {
		ans = max({ans, (ch[p] - ch[i]).norm(), (ch[p] - ch[i + 1]).norm()});
		while ((ch[p] - ch[i + 1]) * (ch[i] - ch[i + 1]) <= (ch[p + 1] - ch[i + 1]) * (ch[i] - ch[i + 1])) {
			p = (p + 1) > n? 1: p + 1;
			ans = max({ans, (ch[p] - ch[i]).norm(), (ch[p] - ch[i + 1]).norm()});
		}
	}
	return ans;
}

类似的还有很多问题，咕咕咕咕。

半平面交

线性规划。

求凸壳，单调队列维护。

代码咕咕咕咕。