회전하는 캘리퍼스 (알고리즘)

안녕하세요. 오늘은 회전하는 캘리퍼스를 배워볼 거예요.

뭐 할때 씀?

가장 먼 두 점 사이의 거리를 구할 때 씁니다.

어떻게 씀?

가장 먼 두점 사이의 거리는 볼록 껍질 위 두 점 A, B가 있을 때 A -> next_A 와 B -> next_B 간선이 최대한 평행이 되도록 만드는 A와 B입니다.

만약 A -> next_A 와 B -> next_B 가 반시계 방향이면 B를 더 옮기고 아니면 A를 옮기면 됩니다.

구현해봐

ㅇㅋ

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#define ll long long
#define pii pair <double,double>
using namespace std;

ll CCW(pii A, pii B, pii C)
{
	double ax = A.first, ay = A.second, bx = B.first, by = B.second, cx = C.first, cy = C.second;
	double ccw = ax * (by - cy) + bx * (cy - ay) + cx * (ay - by);
	if (ccw < 0) return -1;
	if (ccw == 0) return 0;
	return 1;
}
double dist(pii A, pii B)
{
	return (A.first - B.first) * (A.first - B.first) + (A.second - B.second) * (A.second - B.second);
}
bool ycmp(pii A, pii B)
{
	if (A.second != B.second) return A.second < B.second;
	return A.first < B.first;
}
pii low_dot;
bool cmp(pii A, pii B)
{
	if (CCW(low_dot, A, B) > 0) return true;
	if (CCW(low_dot, A, B) == 0) return dist(low_dot, A) < dist(low_dot, B);
	return false;
}


ll stk[101010] = { 0 }, top = 2;
vector <pii> make_convex(vector <pii> v)
{
	ll N = v.size();
	if (N <= 2) return v;
	sort(v.begin(), v.end(), ycmp);
	low_dot = v[0];
	sort(v.begin() + 1, v.end(), cmp);

	stk[0] = 0; stk[1] = 1;
	for (int i = 2; i < N; i++)
	{
		while (top >= 2 && CCW(v[i], v[stk[top - 2]], v[stk[top - 1]]) <= 0)
			top--;
		stk[top++] = i;
	}

	vector <pii> ans;
	for (int i = 0; i < top; i++)
		ans.push_back(v[stk[i]]);


	return ans;
}

double rotating_calipers(vector <pii> v)
{
	ll N = v.size();
	double ans = 0;

	ll Left = 0, Right = 0;
	for (int i = 0; i < N; i++)
	{
		if (v[i].first < v[Left].first)
			Left = i;
		if (v[i].first > v[Right].first)
			Right = i;
	}
	ans = dist(v[Left], v[Right]);
	for (int i = 0; i < N; i++)
	{
		pii prev;
		prev.first = v[(Left + 1) % N].first - v[Left].first;
		prev.second = v[(Left + 1) % N].second - v[Left].second;

		pii next;
		next.first = v[Right].first - v[(Right + 1) % N].first;
		next.second = v[Right].second - v[(Right + 1) % N].second;

		if (CCW({ 0,0 }, prev, next) > 0)
			Left = (Left + 1) % N;
		else
			Right = (Right + 1) % N;

		ans = max(ans, dist(v[Left], v[Right]));
	}
	return ans;
}

int main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	ll N, i, a, b;
	vector <pii> v;
	cin >> N;
	for (i = 0; i < N; i++)
	{
		cin >> a >> b;
		v.push_back({ a,b });
	}
	cout << fixed;
	cout.precision(10);
	cout << sqrt(rotating_calipers(make_convex(v)));
}