달리기 코스 (백준 1310)

안녕하세요. 오늘은 달릴거예요.

문제

https://www.acmicpc.net/problem/1310

아이디어

이거입니다.

소스코드

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

ll CCW(pii A, pii B, pii C)
{
	ll ax = A.first, ay = A.second, bx = B.first, by = B.second, cx = C.first, cy = C.second;
	ll ccw = ax * (by - cy) + bx * (cy - ay) + cx * (ay - by);
	if (ccw < 0) return -1;
	if (ccw > 0) return 1;
	return 0;
}
ll dis(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;
	else if (CCW(low_dot, A, B) == 0) return dis(low_dot, A) < dis(low_dot, B);
	return false;
}

vector <pii> make_convex(vector <pii> v)
{
	ll N = v.size();
	sort(v.begin(), v.end(), ycmp);
	low_dot = v[0];
	sort(v.begin() + 1, v.end(), cmp);


	ll stk[101010] = { 0 }, top = 2;
	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;
}
ll RoCal(vector <pii> v)
{
	ll N = v.size();
	ll i, next_i, j = 0, next_j;
	ll ans = 0;

	for (i = 0; i < N; i++)
	{
		next_i = (i + 1) % N;
		while (true)
		{
			ans = max(ans, dis(v[i], v[j]));
			next_j = (j + 1) % N;

			pii v1, v2;
			v1.first = v[i].first - v[next_i].first;
			v1.second = v[i].second - v[next_i].second;
			v2.first = v[j].first - v[next_j].first;
			v2.second = v[j].second - v[next_j].second;

			if (CCW({ 0,0 }, v1, v2) <= 0)
				break;
			j = next_j;
		}
		ans = max(ans, dis(v[i], v[j]));
	}

	return ans;
}

int main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int N, i, a, b;
	vector <pii> v;

	cin >> N;
	for (i = 0; i < N; i++)
	{
		cin >> a >> b;
		v.push_back({ a,b });
	}

	cout << RoCal(make_convex(v));
}

감사합니다.