geometry/antipodalPoints.cpp


1
2
3
4
5
6
7
8
9
10
11
12
13

vector<pair<int, int>> antipodalPoints(vector<pt>& h) {
	vector<pair<int, int>> result;
	int n = sz(h);
	if (n < 2) return result;
	for (int i = 0, j = 1; i < j; i++) {
		while (true) {
			result.push_back({i, j});
			if (cross(h[(i + 1) % n] - h[i], 
			          h[(j + 1) % n] - h[j]) <= 0) break;
			j = (j + 1) % n;
	}}
	return result;
}