---
tags: code
---

# Rotating Calipers (旋轉卡尺)
[TOC]
## Concept
通常搭配凸包 (Convex Hull) 使用。
類似雙指針的概念，
每次移動把一個指針往下移一格，
另一個則不斷往下移動，
直到最大為止。

## Farthest Pair
最遠點對，
當然可以直接枚舉所有點對 $O(N^2)$。
那其實可以知道最遠點對一定在凸包上，
先求出凸包然後在凸包上枚舉點對 $O(N\log N+N^2)=O(N^2)$，
已經優化但仍有測資 (所有點都在凸包上) 可以使它爛掉。
這時可以使用 `旋轉卡尺` 的概念，
枚舉凸包上的一個點，
該點到逆/順時針到所有點的距離必先遞增再遞減，
作法是枚舉凸包上的所有點，
然後用一個指針找到該點的最遠距離，
接著在移動點時，
即可藉由移動指針找到每個點的最遠點對，
最後將答案取 $max$ 即為所求，
時間複雜度 $O(N\log N+N)=O(N\log N)$。

double farthest_pair_distance(vector<point>& v) {
	v = convex_hull(v); // 取得凸包
	double ret = 0;
	for (int n = (int)v.size(), i = 0, j = i + 1; i < n; i++) {
		while (dis(v[i], v[j]) < dis(v[i], v[(j + 1) % n])) j = (j + 1) % n;
		ret = max(ret, dis(v[i], v[j]));
	}
	return ret;
}

## Largest Triangle
最大三角形，
一樣先找到凸包，
再用用 `旋轉卡尺` 枚舉每個點當定點，
第二個點每次向下轉一格，
而第三個點就跟著轉到找到最大的面積為止，
複雜度 $O(N\log N + N^2)=O(N^2)$。

double max_triangle_area(vector<point>& v) {
	v = convex_hull(v); // 取得凸包
	double ret = 0;
	for (int i = 0, n = (int)v.size(); i < n; i++) {
		for (int j = (i + 1) % n, k = (j + 1) % n; j < n; j++) {
			while (area(v[i], v[j], v[k]) < area(v[i], v[j], v[k + 1])) k = (k + 1) % n;
			ret = max(ret, area(v[i], v[j], v[k]));
		}
	}
	return ret;
}

## Largest Quadrilateral
最大四邊形，
把四角形拆成兩個三角形，
對兩邊分別作用 `旋轉卡尺` 最大三角形，
四邊形面積即兩個三角形面積的和，
時間複雜度 $O(N\log N+N^2)=O(N^2)$。

## Problems
:::spoiler `ZJ b288. 夏季大三角`

#define ALL(x) (x).begin(), (x).end()
struct point {
	double x, y;
	bool operator<(const point& rhs) const {return x == rhs.x ? y < rhs.y : x < rhs.x;}
	point operator-(const point& rhs) const {return {x - rhs.x, y - rhs.y};}
	friend double cross(const point& o, const point& a, const point& b) {
		point lhs = a - o, rhs = b - o;
		return lhs.x * rhs.y - rhs.x * lhs.y;
	}
	friend istream& operator>>(istream& is, point& p) {return is >> p.x >> p.y;}
	point(double _x = 0, double _y = 0): x(_x), y(_y) {}
};

vector<point> convex_hull(vector<point>& hull) {
	if (hull.size() <= 2) return hull;
	sort(ALL(hull));
	vector<point> stk;
	int n = (int)hull.size();
	for (int i = 0; i < n; i++) {
		while ((int)stk.size() >= 2 && cross(stk.end()[-2], stk.end()[-1], hull[i]) <= 0) stk.pop_back();
		stk.push_back(hull[i]);
	}
	for (int i = n - 2, t = (int)stk.size() + 1; i >= 0; i--) {
		while ((int)stk.size() >= t && cross(stk.end()[-2], stk.end()[-1], hull[i]) <= 0) stk.pop_back();
		stk.push_back(hull[i]);
	}
	return stk;
}

double area(const point& a, const point& b, const point& c) {
	return abs(cross(a, b, c)) / 2;
}

void solve() {
	int n; cin >> n;
	vector<point> v(n);
	for (auto& i : v) cin >> i;
	v = convex_hull(v), n = v.size();
	double ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = (i + 1) % n, k = (j + 1) % n; j < n; j++) {
			while (area(v[i], v[j], v[k]) < area(v[i], v[j], v[k + 1])) k = (k + 1) % n;
			ans = max(ans, area(v[i], v[j], v[k]));
		}
	}
	cout << fixed << setprecision(6) << ans << '\n';
}

:::

:::spoiler `TIOJ 1105. H.PS3`
> 待補
:::

:::spoiler `ZJ e747: Largest Quadrilateral`
> 待補
:::