기하 알고리즘 - 기초

기하를 싫어하는 이유

 ps를 하는 사람 중 기하를 싫어하는 사람은 꽤나 된다. 물론 나 또한 그랬기에, 기하를 싫어하는 이유가 무엇인지는 대충 알고 있다. 내가 기하를 싫어했던 이유는 이렇다.

 

 1. 코드가 깔끔하게 나오지 않는 편이다.

 2. 실수 연산이 까다롭다.

 3. 예외처리가 많다.

 

 1번의 경우, 함수를 최대한 많이 사용하면 그나마 깔끔해진다. 사소한 계산이라도 함수를 사용해서 따로 빼주는 게 눈버깅에도 편하다.

 2번의 경우, 최대한 정수로 계산하는 편이 낫다. 근데 보통의 문제들은 double형으로 그냥 계산해도 정답이 나올 정도의 오차 범위를 주기 때문에 이를 신경 쓸 일은 그렇게 많지 않...다.

 3번의 경우를 내가 진짜 싫어했다. 노트에 대충 끄적이면 그대로 코딩을 하는 매우 나쁜 습관이 있어서다. 지금도 아직 남아있는 습관이긴 하지만, 최대한 정리를 마치고 코딩에 들어가는 것으로 이를 극복하려 노력하고 있다..

 

 나의 이야기는 일단 여기까지 하고, 정말 기본적인 기하 알고리즘 몇 개를 적어보겠다. 나의 복습 목적이 크기에, 불친절한 설명이 있을 수도 있다..

 

CCW

 이건 관련 정보가 너무 많으니 짧게 넘어가겠다.

 세 점의 방향성을 확인할 수 있다. 양수면 반시계, 0이면 일직선, 음수면 시계방향으로 세 점이 위치한다.

 또한 이는 신발끈 공식의 일부이기도 하므로, 세 점을 꼭짓점으로 하는 삼각형의 넓이를 구할 수 있다.

using ll = long long;
typedef pair<ll, ll> pll;
ll ccw(pll A, pll B, pll C) {
    return A.X * B.Y + B.X * C.Y + C.X * A.Y - A.Y * B.X - B.Y * C.X - C.Y * A.X;
}

 

 

단순 다각형의 넓이

볼록 다각형은 여러 삼각형으로 자를 수 있다.

 볼록 다각형을 여러 삼각형들로 잘라보자. 이 다각형의 넓이는 삼각형들 넓이의 합이 된다. 구현의 편의를 위해, \(1, i, i+1\)번째 점을 꼭짓점으로 하는 삼각형들의 넓이의 합을 구하면 된다.

 오목 다각형도 똑같이 하면 된다. 파인 부분에서는 CCW가 반대이므로, 넓이가 더해지지 않고 빼지게 된다!

 

BOJ 11758 - CCW

 CCW를 그대로 쓰면 된다.

 

BOJ 2166 - 다각형의 면적

 그대로 다각형의 넓이를 구하면 된다.

 

BOJ 24601 - Dorm Room Divide

 다각형을 정확히 반으로 가를 수 있는 선분의 위치를 찾자. 이 선분 위에서, 내분점 공식을 활용하여 점의 위치를 찾을 수 있다. 다음은 이 문제의 정답 코드이다.

#include <bits/stdc++.h>
#define ll long long int
#define pll pair<ll, ll>
#define X first
#define Y second
#define endl '\n'
 
using namespace std;
 
pll a[202020];
 
ll ccw(pll A, pll B, pll C) {
    return A.X * B.Y + B.X * C.Y + C.X * A.Y - A.Y * B.X - B.Y * C.X - C.Y * A.X;
}
 
void solve()
{
    long double x, y;
    int n; cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i].X >> a[i].Y;
    }
    ll p = 0;
    for (int i = 1; i < n - 1; i++) {
        p += abs(ccw(a[0], a[i], a[i + 1]));
    }
    ll s = 0;
    ll m = 0;
    int j = 1;
    while (p >= s * 2) {
        s += abs(ccw(a[0], a[j], a[j + 1]));
        m = abs(ccw(a[0], a[j], a[j + 1]));
        j++;
    }
    s -= m;
    j--;
    ll r = p - s - m;
 
    cout << fixed << setprecision(13);
    if (p == s * 2) {
        cout << a[j].X << " " << a[j].Y << endl;
        return;
    }
    if (p == s * 2) {
        cout << a[j + 1].X << " " << a[j + 1].Y << endl;
        return;
    }
    long double r1 = (long double)p / 2 - s;
    long double r2 = (long double)p / 2 - r;
    x = a[j].X + (long double)(a[j + 1].X - a[j].X) * r1 / (r1 + r2);
    y = a[j].Y + (long double)(a[j + 1].Y - a[j].Y) * r1 / (r1 + r2);
    cout << x << " " << y << endl;
}
 
int main()
{
    //ios::sync_with_stdio(0); cin.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
    int tc = 1; //cin >> tc;
    while (tc--) solve();
    return 0;
}

 

 

 

180도 정렬

 기하 문제를 풀 때, 볼록 껍질을 구해야 하는 경우가 있다. 이를 위해서는 먼저 점을 정렬해야 하는데, 이때 한 점을 고정하고 각도 정렬을 하게 된다. 왼쪽 아래 점을 고정했다면, 이 점과 다른 점이 이루는 각도는 구간 \((-\pi/2,\pi/2]\)에 들어오게 된다.

 탄젠트(기울기)를 이용하자. \(dy/dx\)를 기준으로 정렬하면 된다. \(dx = 0\)일 수 있으니, 분모를 넘겨서 비교하면 된다. 다음은 원점에 대한 기울기 정렬 코드이다. 탄젠트 함수의 특성에 의해, 점들은 반시계방향으로 정렬된다.

using ll = long long;
typedef pair<ll, ll> pll;
bool cmp(const pll p1, const pll p2) {
    return p1.Y * p2.X < p1.X * p2.Y;
}

360도 정렬

 360도 정렬은 앞에 비해 까다로울 것 같지만, 사실 별 거 없다. 앞서 한 180도 정렬은 제 1, 4 사분면 (혹은 제 2, 3 사분면)위의 점을 정렬하는 방법이다. 동시에 정렬하기 위해서는, 비교하려는 두 점이 속하는 사분면이 어디인지만 확인해주면 된다. 두 점 모두 y축 기준으로 나눈 두 영역 중 한 곳에 속한다면, 기울기 정렬을 해주고, 아니라면 x좌표가 양수인 쪽을 앞으로 보내면 된다.

 

// upd: 두 벡터 (0, y1)와 (0, y2)에 대한 정렬이 제대로 되지 않는다. 6번 줄과 7번 줄 사이에 이를 추가하면 잘 작동한다.

if (p1.X == 0 && p2.X == 0) return p1.Y < p2.Y;

using ll = long long;
typedef pair<ll, ll> pll;
bool cmp(const pll p1, const pll p2) {
    if ((p1.X < 0) != (p2.X < 0)) {
        return p1.X < p2.X;
    }
    return p1.Y * p2.X < p1.X * p2.Y;
}

 

 

 

픽의 정리

 격자점 위의 단순 다각형에 대해, 다음 식이 성립한다.

 

(넓이) = (테두리 위의 격자점의 개수) / 2 + (내부 격자점의 개수) - 1

 

 애초에 이걸 쓰는 문제가 별로 없지만, 보통은 내부 격자점의 개수를 구하기 위한 문제에서 이를 사용한다. 다각형의 넓이는 앞서 언급한 방법으로 간단히 구할 수 있다. 테두리 위의 격자점의 개수도 간단하다. 한 선분 위의 격자점의 개수는, \(gcd(dx, dy) + 1\) 개이다. 이렇게 구한 두 값을 대입하여 내부 격자점의 개수를 구하면 된다.

 

BOJ 7694 - Triangle

 픽의 정리를 그대로 사용하는 문제다. 다음은 이 문제의 정답 코드이다.

#include <bits/stdc++.h>
 
#define X first
#define Y second
#define endl '\n'
using namespace std;
 
 
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
 
ll gcd(ll x, ll y){
    while (y){
        int tmp = x;
        x = y;
        y = tmp % y;
    }
    return x;
}
 
ll ccw(pll p1, pll p2, pll p3){
    return abs(p1.X * p2.Y + p2.X * p3.Y + p3.X * p1.Y - p1.Y * p2.X - p2.Y * p3.X - p3.Y * p1.X);
}
 
ll calc(pll p1, pll p2){
    ll dx = abs(p2.X - p1.X);
    ll dy = abs(p2.Y - p1.Y);
    if (dx == 0) return dy;
    return gcd(dx, dy);
}
 
int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    while (true) {
        pll a, b, c;
        cin >> a.X >> a.Y >> b.X >> b.Y >> c.X >> c.Y;
        if ((a.X | a.Y | b.X | b.Y | c.X | c.Y) == 0) break;
        ll A = calc(a, b) + calc(b, c) + calc(c, a);
        ll S = ccw(a, b, c);
        cout << (S - A + 2) / 2 << endl;
    }
 
    return 0;
}
 

 

 

 

기타 쉬운..? 문제들

BOJ 9015 - 정사각형

 어떤 두 점을 꼭짓점으로 갖는 정사각형은 최대 두 개이다. 두 점을 고정하고, hash map 등으로 나머지 두 점이 존재하는 지 찾으면 된다.

 

BOJ 16115 - 팬이에요

 원점과의 거리가 가장 먼 점들만 보면 된다. 이런 점들 중에서, 이전 점과의 각도 차이의 최댓값이 답이다. 점들을 각도 정렬할 필요는 없다.

 

BOJ 3843 - 볼록 정다각형 (좀 구데기입니다..)

 정다각형의 꼭짓점을 모두 지나는 원은 유일하다. 또한, 이 정다각형에서 세 점을 뽑아 만든 삼각형의 외심(외심의 좌표를 구하는 방법은 이 문제의 힌트에서 볼 수 있다) 이 곧 원의 중심이다. 이제, 가능한 모든 정다각형에 대해 세 점 모두 이 정다각형의 꼭짓점에 속하는 지를 확인하면 된다. 근데 이 문제, 실수 오차가 좀 화난다. 그닥 추천하지는 않는다.

 

BOJ 16603 - Circuit Board Design

 정말 마음에 드는 문제다. 적당한 각도를 잡고, 한쪽의 dfs가 끝날 때마다 이 각도를 더해주면서 진행하면 된다. 적당한 각도를 잡을 때 주의할 점은, 더해지는 각도의 합은 무조건 180도 미만이 되어야 한다는 것이다.

 이 문제가 착한 또 다른 이유는, 두 정점 사이의 거리가 1이라는 것이다. 코드도 정말 깔끔하게 나온다..

(검정, 빨강, 주황, 노랑, 초록, 하늘, 파란색의 순서) 180도 안에서 이루어지도록 dfs를 진행한다.

 다음은 이 문제의 정답 코드이다.

#include<bits/stdc++.h>
#define all(v) v.begin(),v.end()
using namespace std;
using ll = long long;
 
#define X first
#define Y second
#define endl '\n'
 
typedef pair<double, double> pdd;
 
vector<int> g[1010];
bool v[1010];
pdd ans[1010];
double PI = acos(-1);
double d = 0;
 
 
double dist(pdd L, pdd R) {
    return (L.X - R.X) * (L.X - R.X) + (L.Y - R.Y) * (L.Y - R.Y);
}
 
void dfs(int x) {
    v[x] = true;
    double sz = g[x].size() - 1;
    for (auto i : g[x]) {
        if (v[i]) continue;
 
        ans[i].X = ans[x].X + cos(PI / 1100 * d);
        ans[i].Y = ans[x].Y + sin(PI / 1100 * d);
 
        dfs(i);
    }
    d++;
}
 
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    ans[1] = { 0, 0 };
    dfs(1);
 
    for (int i = 1; i <= n; i++) {
        cout << fixed << setprecision(8);
        cout << ans[i].X << " " << ans[i].Y << endl;
    }
    return 0;
}

 

 

 

마치며

 언제가 될 지는 모르겠지만.. 다음 글에서는 Rotating Calipers, Convex Hull을 다룰 생각이다.

 

 수정 1: 오목 다각형의 넓이를 추가했습니다.

 수정 2: 코드에서 X, Y는 first, second를 의미합니다. 저의 실수로 CCW, 정렬 부분에 이것이 누락되었습니다.

 

 

[참고한 글]

https://zigui.tistory.com/34

기하를 여행하는 Competitive Programmer를 위한 안내서

https://rebro.kr/12

CCW (Counter-ClockWise) - (2)