실수 없는 계산기하(1) ★

계산기하의 기본 도구들을 소개합니다.

마음가짐

기하 문제는 예외 처리가 적고, 구현이 쉬운 형태의 표현 방법 및 풀이를 이용해야 한다.
그리고 실수 좌표보다는 정수 좌표를 이용해야 한다.
그래서 이 글은 실수를 적극적으로 이용하는 문제는 논외로 한다. 그래서 이중적 의미로 "실수 없는 계산기하"이다.

템플릿

기하를 여행하는 Competitive Programmer를 위한 안내서에서 소개된 편리한 표현 방법을 따른다.

위 글에서 참고한 예외 사항이다:

• 점이 [1, 2개 / 일직선상 / 위에 존재]
• 직선, 선분이 [평행 / 일직선상]
• 중복 존재

점과 벡터

complex<ll>을 사용한다. Unspecified Behavior임을 감안하여 몇몇 함수들을 재정의한다.
Unspecified Behavior임에도 사용하는 이유는, 덧셈/뺄셈/곱셈를 기반으로 한 많은 연산자들을 정의할 필요가 없기 때문이다.

참고로, 중복되는 점 여부를 꼭 확인하고, 존재한다면 미리 제거할 필요가 있다.

쉽게 제거되지 않는다면 pair<P,int>나 pair<P,vector<int>>를 사용하는 것도 좋다.

using P = complex<ll>;
#define X real()
#define Y imag()
#define dot(u,v) (conj(u)*(v)).X
#define cross(u,v) (conj(u)*(v)).Y
#define norm(u) dot(u,u)
int ccw(P a, P b, P c) {
    auto v = cross(b-a,c-b);
    if (v < 0) return -1;
    else if (v > 0) return 1;
    return 0;
}
ld abs(P u) {return sqrt(ld(norm(u)));}
istream &operator >> (istream &is, P &p) {ll x, y; is >> x >> y; p = {x,y}; return is;}
namespace std { bool operator < (const P &u, const P &v) {return u.X == v.X ? u.Y < v.Y : u.X < v.X;} }

극 정렬

가장 간단한 형태의 극 비교는 다음과 같다. 점 o를 기준으로 반시계방향 정렬을 한 것이다.

mathsciforstudent.tistory.com

auto polar_compare = [o](P u, P v) {
    if ((u<o) != (v<o)) return u < v;
    return cross(u-o,v-o) > 0;
};

여기에 정렬 옵션을 추가할 수 있다.

길이 옵션

각도가 같은 경우 길이 순으로 정렬되도록 한 경우이다.

mathsciforstudent.tistory.com

auto polar_compare = [o](P u, P v) {
    if ((u<o) != (v<o)) return u < v;
    if (cross(u-o,v-o) != 0) return cross(u-o,v-o) > 0;
    return norm(u-o) < norm(v-o);
};

기준선 옵션

기준선이 삐뚤어진 경우이다.

mathsciforstudent.tistory.com

auto half = [o,x](P p) {
    if (cross(x-o,p-o) < 0) return true;
    return cross(x-o,p-o) == 0 and dot(x-o,p-o) < 0;
};
auto polar_compare = [o,&half](P u, P v) {
    if (half(u) != half(v)) return half(u) < half(v);
    return cross(u-o,v-o) > 0;
};

연습문제

• 점 $(2,3)$과 $(5,-1)$의 거리를 구하라.
• 점 $(5,4)$와 $(0,1)$이 원점과 이루는 각의 크기를 구하라.

선분과 직선

$\vec a+(\vec b-\vec a)k$에서 $k\in [0,1]$일 경우 선분, $k\in (-\infty,+\infty)$일 경우 직선이다.

mathsciforstudent.tistory.com

선분은 다음과 같이 짜면 된다:

struct Segment {
    P a, b;
    void sort() {if (b < a) swap(a,b);}
    friend bool operator == (Segment s1, Segment s2) {
        s1.sort(), s2.sort();
        return s1.a == s2.a and s1.b == s2.b;
    }
    friend bool intersect(Segment s1, Segment s2) {
        s1.sort(), s2.sort();
        int c1 = ccw(s1.a,s2.a,s1.b)*ccw(s1.a,s2.b,s1.b);
        int c2 = ccw(s2.a,s1.a,s2.b)*ccw(s2.a,s1.b,s2.b);
        if (c1 or c2) return c1 <= 0 and c2 <= 0;
        else return not(s1.b < s2.a or s2.b < s1.a);
    }
};

mathsciforstudent.tistory.com

직선은 다음과 같이 짜면 된다:

struct Line {
    P a, b;
    Line(P p, P q): a(p), b(q) {}
    Line(P _a, ll _b): a(0,_b), b(a+_a) {}
};

점과 직선 사이 거리

흔히 "점직거 공식"이라고 불리는 것을 써도 되겠지만, 외적을 이용하면 더 간단하게 표현할 수 있다.

$S_{\triangle APB}=\overrightarrow {PA}\times \overrightarrow {PB}/2$이라는 것과, 거리에 수직한 밑변이 $\overline{AB}$임에 기인한다.

ld dist(P p, Line l) {return cross(l.a-p,l.b-p)/abs(l.a-l.b);}

연습문제

• 점과 선분 사이 거리를 측정하는 방법을 찾아라. 직선 사이 거리와 무엇이 다른가?
• 두 직선이 평행한지 판별하는 방법을 찾아라.
• 두 직선이 수직한지 판별하는 방법을 찾아라.

다각형

넓이 구하기, 볼록껍질 구하기, 지름 구하기의 범위를 넘는 다각형 문제는 드물다. 따라서 이 세 가지 메소드만을 다룬다.

using Poly = vector<P>;

넓이

정수 좌표를 꼭짓점으로 갖는 다각형의 넓이는 항상 (정수)/2 꼴이다. 따라서 넓이의 2배를 반환하는 것이 바람직하다.

ll area2(const Poly &p) {
    ll s = 0;
    REP(i,0,size(p)-2) s += cross(p[i+1],p[i]);
    return s+cross(p[0],p.back());
}

볼록 껍질

모든 점을 포함하는 가장 작은 볼록다각형.
점들이 못이라고 생각했을 때, 고무줄을 늘여 두른 후 놓았을 때의 모습으로 생각할 수 있다.

모노톤 체인(Monotone chain) 또는 그라함 스캔(Graham scan)으로 구할 수 있다.

두 알고리즘의 차이는 점들을 정렬하는 방식에서 차이가 난다. 그 외의 사항은 매우 비슷하다.

모노톤 체인

좌우 양끝의 극점을 잡는다. 그리고 두 극점을 양 끝점으로 하는 윗 껍질과 아랫 껍질을 따로 구축해 나간다.

Poly convex_hull(vector<P> p) {
    sort(p.begin(),p.end());
    Poly up(size(p)), lo(size(p));
    int u = 0, l = 0, i = 0, j = size(p)-1;
    REP(_,1,size(p)) {
        while (u >= 2 and ccw(up[u-2],up[u-1],p[i]) >= 0) --u;
        while (l >= 2 and ccw(lo[l-2],lo[l-1],p[j]) >= 0) --l;
        up[u++] = p[i++], lo[l++] = p[j--];
    }
    up.resize(u-1), lo.resize(l-1);
    up.insert(up.end(),lo.begin(),lo.end());
    return up;
}

그라함 스캔

극점을 기준으로 나머지 점들을 기울기 순으로 정렬한다. 그 다음 한쪽 방향으로 돌면서 볼록 껍질을 구축해 나간다.

Poly convex_hull(vector<P> p) {
    swap(*min_element(p.begin(),p.end()),p[0]); P o = p[0];
    sort(p.begin()+1,p.end(),[o](P u, P v){
        if (cross(u-o,v-o) == 0) return norm(u-o) < norm(v-o);
        return cross(u-o,v-o) > 0;
    });
    Poly h(size(p)); h[0] = o; int n = 1;
    REP(i,1,size(p)-1) {
        while (n >= 2 and ccw(h[n-2],h[n-1],p[i]) <= 0) --n;
        h[n++] = p[i];
    }
    h.resize(n);
    return h;
}

연습문제

• 위에서 설명한 코드는 사실 엄격한 볼록껍질을 구한다. 그렇다면 일반적인 볼록껍질을 구하라. 무엇이 다른가? 어떤 예외 사항들이 존재하는가?
• 위 코드는 점의 개수가 1개일 경우와 2개일 경우에도 잘 작동하는가?

예제

링크가 걸려있다.

템플릿 연습

중요한 문제들을 빨간색으로 표시했다.

앞서 소개한 템플릿들을 그대로 사용만 해도 AC를 받을 수 있는 문제들이다.

• CCW: ccw(a,b,c) 이용
• 선분 교차 1, 선분 교차 2, 선분 그룹: intersect(l,m) 이용
  
  • 덤으로 선분 교차 EX도 풀어보자!
• 다각형의 면적: area2(p)/2 이용
• Convex Hull, 격자점 컨벡스헐, 볼록 껍질: convex_hull(p) 이용
• Cows: convex_hull(p)와 area2(p)/2 이용

간단한 응용 문제

소위 '날먹'이 가능한 수준의 문제들이다.

• 교차
• 맹독 방벽
• 단순 다각형
• Wall construction
  

참고

볼드체로 표시한 자료들이 이 글에 영향을 준 자료들이다.

• 기하를 여행하는 Competitive Programmer를 위한 안내서: 이 글에서 배운 점을 토대로 작성했다. 정말 좋은 글이다.
• CPH - 29. Geometry: 이 글로 처음 기하에 입문했다.
• cp-algorithms - Geometry: 알찬 튜토리얼이다.
• Handbook of geometry for competitive programmers: 구현 스타일을 배웠다.
• Geometry: 2D points and lines: 참고하지는 않았지만 유명한 글이다.
• Geometry Algorithms: 유명한 계산기하 책이다.
• C++ tools for computational geometry: 글 작성에 참고하지는 않았지만, std::complex를 다루는 방법을 잘 정리한 글이다.