[BOJ] 9240. 로버트 후드

문제

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

9240번: 로버트 후드

 

풀이

전형적인 Convex Hull 문제이다.

아래 풀이에서는 Graham Scan이라고 하는 $O(nlogn)$의 알고리즘을 사용한다.

 

Convex Hull을 구한 후, Convex Hull 상에서 가장 먼 두 점을 찾는데, 원래는 Rotating Calipers 라는 알고리즘을 사용하여 $O(n)$에 구해야 한다.

하지만 필자는 한 번도 구현해본 적이 없고, 실제 이 문제에서는 좌표의 범위가 작고, 정수점만 입력으로 들어오기때문에 Convex Hull의 점의 수가 매우 작고, 실제로 1000*4=4000개보다 작음은 약간의 논증을 통해 보일 수 있다.

 

따라서 Convex Hull 내부의 모든 점을 비교해도 시간안에 구할 수 있다.

정해는 rotating calipers라는 알고리즘을 이용해서 가장 먼 두 점을 구하는데 $O(|convex hull|)$이면 충분하다.

 

Time Complexity : $O(nlogn + |convex hull|^2)$

 

코드

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#define N 100002
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pos;
 
double dist(pos p1, pos p2)
{
	double dissq = (p1.first - p2.first) * (p1.first - p2.first) + (p1.second - p2.second)*(p1.second - p2.second);
	return sqrt(dissq);
}

int n;

vector<pos> p;

ll ccw(pos p1, pos p2, pos p3)
{
	return (p2.first - p1.first)*(p3.second - p1.second) - (p2.second - p1.second)*(p3.first - p1.first);
}

bool cmp(pos p1, pos p2)
{
	ll c = ccw(p[0], p1, p2);
	if (c > 0) return 1;
	if (c < 0) return 0;
	else
    {
		if (dist(p[0], p1) < dist(p[0], p2)) return 1;
		else return 0;
	}
}

int main()
{
	cin>>n;

	p.resize(n);
	for (int i=0;i<n;i++) cin>>p[i].first>>p[i].second;
	
	sort(p.begin(),p.end());
	sort(p.begin()+1,p.end(),cmp);
    
	vector<pos> cvxh;
	cvxh.push_back(p[0]);
	cvxh.push_back(p[1]);

	for (int i=2;i<n;i++)
	{
		while (cvxh.size() >= 2 && ccw(cvxh[cvxh.size()-2],cvxh.back(),p[i])<=0)
			cvxh.pop_back();
		cvxh.push_back(p[i]);
	}
    
	double ans=-1;
	int len=cvxh.size();
	for (int i=0;i<len;i++) for (int j=i+1;j<len;j++)
		ans=max(ans, dist(cvxh[i], cvxh[j]));

    printf("%.10f", ans);
}