회전하는 캘리퍼스 (rotating calipers)
구현
호균 ver
// 제일 멀리 떨어져 있는 두 점 구하기
// 제일 멀리 떨어져 있는 점들은 반드시 볼록 껍질 위에 존재한다.
// 컨벡스헐을 구하고 나면 O(N)만에 해결 가능
// 캘리퍼스가 특정방향(반시계)으로 회전하면서 볼록 다각형의 한 변에 닿으면
// 그 변의 점을 (반시계방향으로)다음 점으로 옮긴다.
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <vector>
using namespace std;
#define lli long long int
struct vec{
double x, y;
vec operator -(const vec& rhs) const { return {x-rhs.x, y-rhs.y}; }
bool operator <(const vec &rhs) const {
if(y != rhs.y) return y < rhs.y;
return x < rhs.x;
}
double cross(const vec& rhs) const { return x * rhs.y - rhs.x * y; }
double norm() const { return hypot(x, y); }
};
double ccw(vec a, vec b){ return a.cross(b); }
double ccw(vec p, vec a, vec b){ return ccw(a-p, b-p); }
vec s;
bool cmp(vec a, vec b){
if(ccw(a-s, b-s) != 0) return ccw(a-s, b-s) > 0;
return a < b;
}
vector<int> convex_hull(vector<vec>& p){
sort(p.begin(), p.end());
s = p[0];
sort(p.begin()+1, p.end(), cmp);
vector<int> ret;
ret.push_back(0);
ret.push_back(1);
for(int now=2; now<p.size(); now++){
while(ret.size() >= 2){
int last1 = *(ret.end() - 1);
int last2 = *(ret.end() - 2);
if(ccw(p[last2], p[last1], p[now]) > 0) break;
ret.pop_back();
}
ret.push_back(now);
}
return ret;
}
// 답이 되는 점까지 구해보자.
vec ans1, ans2;
double rotating_calipers(vector<vec>& p){
vector<int> tmp = convex_hull(p);
vector<vec> cx;
for(int now : tmp) cx.push_back(p[now]);
int p1, p2;
double maxv;
p1 = 0; p2 = 1;
maxv = (cx[p1]-cx[p2]).norm();
ans1 = cx[p1];
ans2 = cx[p2];
// 2*n번인 이유
// (p2가 p1에서 제일 떨어진 점까지 도달하는 데 최대 n-2번)
// (그 후 회전하며 서로 자리 바뀔 때까지 최대 n번)
for(int t=0; t<cx.size()*2; t++){
int np1 = (p1+1) % cx.size();
int np2 = (p2+1) % cx.size();
double tmp = ccw(cx[np1]-cx[p1], cx[p2]-cx[np2]);
// 어떤 각도가 더 작은가
if(tmp > 0) p1 = np1;
if(tmp < 0) p2 = np2;
if(tmp == 0) { p1 = np1; p2 = np2; }
double nowv = (cx[p1]-cx[p2]).norm();
if(maxv < nowv){
maxv = nowv;
ans1 = cx[p1];
ans2 = cx[p2];
}
}
return maxv;
}
용준 ver
정리
- 가장 먼 두 점을 찾는 문제를 푸는 방법이다.
- 컨벡스 헐에서 두 점 가장 먼 두 점의 후보가 된다. 하지만 O(N^2) 이다.
- 반면, 회전하는 캘리퍼스는 컨벡스 헐이 주어져있을 때 O(N) 으로 먼 두 점을 찾을 수 있다.
- 알고리즘
- 다각형을 반시계 방향으로 돌려야 한다. 따라서 최초에는 최소, 최대의 x 값의 인덱스를 지정한다
- 캘리퍼스가 닿아있는 두 점 중에서, 반시계 방향으로 돌릴 때 가장 작은 각도로 움직일 수 있는 점을 기준으로 한다
- n 번 반복하고, 최대의 길이를 가지는 두 점이, 가장 먼 두 점이다.
관련 문제
- 10254번: 고속도로