# [Platinum III] 로버트 후드 [문제 링크](https://www.acmicpc.net/problem/9240) ## 문제 설명 <p>로버트 후드는 로빈 후드의 동생이다. 로버트 후드는 자신의 형처럼 전설적인 인물이 되기 위해 활 쏘기를 연습하고 있다.</p> <p>이번에 노팅엄에서 열린 활 쏘기 대회는 현대에 열리는 양궁과 규칙이 다르다. 양궁은 더 많은 점수를 쏜 사람이 승리하는 방식이다. 하지만, 노팅엄 활 쏘기 대회에서는 과녁에 맞은 화살 사이의 거리 중 최댓값이 가장 큰 사람이 승리한다.</p> <p>로버트 후드는 총 C발을 발사했고, 모든 화살은 과녁에 적중했다. 과녁을 이차원 평면으로, 화살은 점으로 나타낸다. 화살의 좌표가 주어졌을 때, 가장 먼 화살의 거리를 구하는 프로그램을 작성하시오.</p> ## 입력 <p>첫째 줄에 로버트 후드가 발사한 화살의 수 C (2 ≤ C ≤ 100,000)가 주어진다. 다음 C개 줄에는 화살의 좌표가 주어진다. 좌표는 정수이고, 절댓값은 1,000을 넘지 않는다.</p> ## 출력 <p>가장 먼 두 화살의 거리를 출력한다. 상대/절대 오차가 10^-6 이내인 경우에만 정답이다.</p> ## 풀이 #### 그라함 스캔과 회전하는 캘리퍼스 알고리즘을 사용하여 풀었다. ``` c++ #include<bits/stdc++.h> using namespace std; struct point { int x, y, p=0, q=0; bool operator<(const point o) const { if(p*o.q!=q*o.p) return p*o.q > q*o.p; if(y!=o.y) return y < o.y; return x < o.x; } }; int ccw(point a, point b, point c) { point vec1 = {b.x-a.x, b.y-a.y}; point vec2 = {c.x-a.x, c.y-a.y}; return vec1.x*vec2.y - vec1.y*vec2.x; } int ccw(point a, point b, point c, point d) { point vec1 = {b.x-a.x, b.y-a.y}; point vec2 = {d.x-c.x, d.y-c.y}; return vec1.x*vec2.y - vec1.y*vec2.x; } vector<point> graham_scan() { int c; cin >> c; vector<point> v(c); for(int i=0;i<c;i++) cin >> v[i].x >> v[i].y; sort(v.begin(), v.end()); for(int i=1;i<c;i++) { v[i].p = v[i].x-v[0].x; v[i].q = v[i].y-v[0].y; } sort(v.begin(), v.end()); vector<point> stk; for(int i=0;i<c;i++) { while(stk.size()>=2 && ccw(stk[stk.size()-2], stk[stk.size()-1], v[i])<=0) stk.pop_back(); stk.push_back(v[i]); } return stk; } int dist(point a, point b) { return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y); } void rotating_calipers(vector<point> hull) { int n = hull.size(); int maxDist=0, i=0, j=1; while(i<n && j<n) { maxDist = max(maxDist, dist(hull[i], hull[j])); if(ccw(hull[i], hull[(i+1)%n], hull[j], hull[(j+1)%n])>0) j++; else i++; } cout << setprecision(6) << fixed << sqrt(maxDist); } int main() { ios::sync_with_stdio(0); cin.tie(0); rotating_calipers(graham_scan()); } ```