[AtCoder] [經典競程 90 題] 009 - Three Point Angle（★6）

題目連結:https://atcoder.jp/contests/typical90/tasks/typical90_i
題目大意:
給定 $N$ 個二維點，請求出一組點 $i$, $j$, $k$ 使得其夾角越大越好，這裡夾角一定是 < 180 的那個角。

---

以每個點為中心做極角排序，然後雙指針找出在符合條件下的最大的夾角。

#include <bits/stdc++.h>
using namespace std;
using llf = long double;
constexpr llf PI = acos(-1);

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n; cin >> n;
	vector<pair<int,int>> ps(n);
	for (auto &[x, y]: ps) cin >> x >> y;
	llf ans = 0;
	for (auto [x, y]: ps) {
		vector<llf> ang;
		for (auto [px, py]: ps) {
			if (px != x or py != y) {
				auto d = atan2(py - y, px - x);
				ang.push_back(d);
				ang.push_back(d + 2 * PI);
			}
		}
		sort(ang.begin(), ang.end());
		size_t j = 1;
		for (size_t i = 0; i + 1 < ang.size();++i) {
			j = max(j, i + 1);
			while (j + 1 < ang.size()) {
				if (ang[j + 1] - ang[i] > PI) {
					break;
				}
				++j;
			}
			if (ang[j] - ang[i] <= PI) {
				ans = max(ans, ang[j] - ang[i]);
			}
		}
	}
	cout << fixed << setprecision(15) << ans / PI * 180 << '\n';
	return 0;
}