[C++] 10254번 고속도로 - 기하학, 볼록 껍질, 회전하는 캘리퍼스

1. 문제

• n개의 도시를 가진 나라가 있다. 이 나라의 도시 중 가장 먼 두 도시를 찾아 그 도시의 좌표를 구하라. 단 모든 도시는 한 평면 위에 있다.

<입력>

• -1-   테스트 케이스의 수 T
• --1-   도시의 개수 \(n(2 \leq n \leq 200,000)\)
• --n개-   x좌표 y좌표 \((-10,000,000 \leq, x, y \leq 10,000,000) x, y \in \mathbb{Z} \)
  • 어떤 수 도시가 같은 점 위에 있는 경우는 없다.

<출력>

• 테스트 케이스마다 가장 먼 두 점의 좌표를 출력한다.

2. 재정의

• 좌표평면에서 가장 먼 두 점의 위치를 구하시오

3. 해결 방법

1. Convex Hull Algorithm으로 볼록 껍질을 구한다.
2. 임의의 두 점의 거리를 최장거리로 가정하자
3. 두 벡터의 외적으로 캘리퍼스와 이루는 각의 크기를 비교하여 캘리퍼스를 더 작은 각만큼 회전시키며 가장 먼 두 점의 거리를 구한다.

4. 실수한 점, 개선할 점

• CCW와 Cross곱은 int범위를 벗어날 수 있으므로 long long으로 받아야 한다.
• y좌표가 가장 작은 점을 찾을 때 sort함수를 끄지 않고 min_element()함수를 사용하면 좀 더 빠르게 구할 수 있다. O(n) vs O(nlgn)
• cmp에서 ccw를 두 번 연산하지 않고 한 번만 연산하면 소요 시간을 줄일 수 있다.
• 데이터의 크기에 맞게 int형과 long long형을 번갈아 사용하는 것 보다 long long형으로 쭉 사용하는 것이 소요 시간이 더 줄어든다.(아마 형 변환 과정 때문인듯)

 

<코드>

#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>

using namespace std;
typedef long long ll;

struct vec {
    int x, y;
    
    vec(){};
    vec(int _x, int _y) : x(_x), y(_y) {};
    
    //벡터용 - 연산자
    vec operator -(const vec &rvec) const { return {x-rvec.x, y-rvec.y}; }
    //벡터용 < 연산자
    bool operator <(const vec &rvec) const {
        if(y != rvec.y) return y < rvec.y;
        return x < rvec.x;
    }
    //벡터 외적
    ll cross(const vec& rvec) const { return 1LL*x*rvec.y - 1LL*rvec.x*y; }
    //두 벡터 사이의 길이
    ll norm() const { return 1LL*x*x + 1LL*y*y; }
};
ll ccw(vec a, vec b) { return a.cross(b); }
ll ccw(vec p, vec a, vec b) { return ccw(a-p, b-p); }

//테스트 케이스의 수 T
int T;
//도시의 개수 n
int n;
//도시의 좌표
vector<vec> p;
//제일 왼쪽 아래 정점
vec s;

//s를 기준으로 반시계방향으로 정렬
bool cmp(vec a, vec b) {
    //같은 직선상에 위치하지 않는다면
    ll tmp = ccw(a-s, b-s);
    if(tmp)
        return tmp > 0;
    return a < b;
}

//convex hull 알고리즘
vector<int> convex_hull(vector<vec>& p) {
    //제일 왼쪽 아래 점 찾기
    swap(p[0], *min_element(p.begin(), p.end()));
    s = p[0];
    //s를 기준으로 반시계방향으로 정렬
    sort(p.begin()+1, p.end(), cmp);
    
    vector<int> ret;
    ret.push_back(0);
    ret.push_back(1);
    
    for(int here=2; here<p.size(); here++) {
        while(ret.size() >= 2) {
            int last1 = *(ret.end() - 1);
            int last2 = *(ret.end() - 2);;
            if(ccw(p[last2], p[last1], p[here]) > 0)
                break;
            ret.pop_back();
        }
        ret.push_back(here);
    }
    
    return ret;
}

//가장 멀리 떨어져 있는 두 점
vec res1, res2;
void rotating_calipers(vector<vec>& p) {
    vector<int> tmp = convex_hull(p);
    vector<vec> cx;
    //convex_hull로 얻은 정점을 cx에 넣기
    for(int e : tmp)
        cx.push_back(p[e]);
    
    int n = cx.size();
    
    int p1, p2;
    ll maxdist;
    
    p1 = 0, p2 = 1;
    maxdist = (cx[p1] - cx[p2]).norm();
    res1 = cx[p1], res2 = cx[p2];
    
    for(int i=0; i<n*2; i++) {
        int np1 = (p1 + 1) % n;
        int np2 = (p2 + 1) % n;
        ll tmp = ccw(cx[np1] - cx[p1], cx[p2] - cx[np2]);
        
        //더 작은 각도만큼 캘리퍼스 회전
        if(tmp>0) p1 = np1;
        if(tmp<0) p2 = np2;
        if(!tmp) { p1 = np1, p2 = np2; }
        
        //현재 두 점 사이의 거리가 더 길면 갱신하기
        ll nowdist = (cx[p1] - cx[p2]).norm();
        if(maxdist < nowdist) {
            maxdist = nowdist;
            res1 = cx[p1];
            res2 = cx[p2];
        }
    }
}

void input() {
    //초기화
    p.clear();
    
    cin >> n;
    
    for(int i=0; i<n; i++) {
        int x, y;
        cin >> x >> y;
        p.push_back(vec(x, y));
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> T;
    while(T--) {
        input();
        
        rotating_calipers(p);
        
        cout << res1.x << ' ' << res1.y << ' ' << res2.x << ' ' << res2.y << '\n';
    }
    
    return 0;
}

회전하는 캘리퍼스 알고리즘은 처음이라서 다른 블로그를 찾아보며 공부하였는데 <회전하는 캘리퍼스 - 1>의 코드가 매우 깔끔하게 짜여져 있다. 시간적 요소는 고려되지 않은 것 같으나 코드가 깔끔하고 간결하여 이를 참고하여 작성하였다.

 

 

<회전하는 캘리퍼스 - 1>

https://hgkim.gitbooks.io/algorithm/content/d68c-c804-d558-b294-ce98-b9ac-d37c-c2a428-rotating-calipers.html

회전하는 캘리퍼스(rotating calipers) · algorithm

 

<회전하는 캘리퍼스 - 2>

https://aruz.tistory.com/59

회전하는 캘리퍼스 rotating calipers

 

<회전하는 캘리퍼스 - 3>

https://hellogaon.tistory.com/40

회전하는 캘리퍼스

 

<hypot 함수>

https://ehpub.co.kr/hypot-hypotf-hypotl-%ED%95%A8%EC%88%98/

hypot, hypotf, hypotl 함수 – 언제나 휴일

 

<Convex Hull Algorithm>

https://www.crocus.co.kr/1288

컨벡스 헐 알고리즘(Convex Hull Algorithm)

 

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.