기하 코딩

기하 코딩은 고통이다. 덜 고통스럽게 하자.

점 관리하기

점을 나타내는 struct를 만들어 쓰는 경우가 많이 있는데, 개인적으로는 std::pair가 더 낫다고 생각한다.

std::pair는 <utility> 헤더에 포함되어있다. 보통 <algorithm> 헤더가 이걸 포함하고 있기 때문에 #include <algorithm>만 해도 쓸 수 있게 된다. PS에서는 대부분 using namespace std;를 하기 때문에 여기서도 이걸 한 걸로 가정한다.

pair<int, int>가 입력하기 불편하기 때문에 이렇게 할 수 있다.

 
AخA
typedef pair<int,int> pii; // C-style
using pii=pair<int,int>;   // C++11

또한 코드를 직관적으로 만들기 위해 이런 전처리를 시킬 수 있다.

 
xxxxxxxxxx
#define x first
#define y second

벡터 기하를 하다 보면 long long 범위의 값을 사용할 때가 많다.

 
xxxxxxxxxx
typedef long long ll;

이렇게 하면 점들을 사용하기가 편하다. 왜?

 
​x
vector<pii> getConvexHull(vector<pii> pt);
sort(v.begin(), v.end());
pii operator-(pii a, pii b){ return {a.x-b.x, a.y-b.y}; }
ll cross(pii a, pii b){ return b.y*1LL*a.x - b.x*1LL*a.y; }
bool ccw(pii a, pii b, pii c){ return cross(b-a, c-a) >= 0; }
​
#include <tuple>
​
pii pt(0, 3);
int x, y; tie(x, y) = pt;
// equiv. to:
// int x=pt.x, y=pt.y;
​
for(auto& tmp : v){
    int x, y; tie(x, y) = tmp;
    // do something with the points
}

operator를 정의해서 벡터 연산을 직관적으로 할 수 있고, 비교 연산자가 구현되어있으므로 STL로 정렬시킬 수도 있다. 또한 tuple의 기능이 구현되어있기 때문에, tie()로 값을 꺼내올 수 있다.

Convex Hull

다양한 방법이 있는데, 내가 쓰는 방법은 Monotone chain 알고리즘이라고 한다. 점들을 한 쪽 축으로 정렬한 후, stack과 CCW를 이용하여 upper hull을 구하고, 반대로 보면서 lower hull을 구한다.

 
xxxxxxxxxx
// Calculates upper & lower hull. O(NlgN) time & O(N) space.
pair<vector<pii>, vector<pii>> getConvexHull(vector<pii> pt){
    sort(pt.begin(), pt.end());
    vector<pii> uh, dh;
    int un=0, dn=0; // for easy coding
    for(auto& tmp:pt){
        while(un >= 2 && ccw(uh[un-2], uh[un-1], tmp)) uh.pop_back(), --un;
        uh.push_back(tmp); ++un;
    }
    reverse(pt.begin(), pt.end());
    for(auto& tmp:pt){
        while(dn >= 2 && ccw(dh[dn-2], dh[dn-1], tmp)) dh.pop_back(), --dn;
        dh.push_back(tmp); ++dn;
    }
    return {uh, dh};
}

Convex Hull과 특정 기울기의 접선

특정한 기울기를 가지는 직선을 평면 상에서 움직이다 보면, convex hull과 어느 점에서 만나 어느 점에서 분리된다.

이 점들을 구하는 과정은 이분탐색을 잘 하면 되겠지만 코딩이 까다로울 수 있다. 그러나 위에서 한 것처럼 upper/lower hull을 구하면 특별한 성질이 하나 나온다.

어떤 벡터를 반쪽짜리 hull의 각각의 점과 내적한 값은, hull 상의 순서대로 보았을 때 3분 탐색이 가능하다.

이게 무슨 말인지 자세히 보자.

$ax+by=c$ 와 같은 기울기의 직선을 긋는다고 하자. 어떤 점 $(x, y)$에 대해 $ax+by$의 값은, 그 기울기로 그 점을 지나는 직선을 그었을 때 그 직선의 위치와 관계있는 값이다. 즉 이 기울기로 그은 직선 위의 점들은 모두 그 값이 같고(식에서 $c$ 자리에 있는 값이 바로 그 값이 될 것), 이 값의 크기 비교를 통해 직선 간의 위치 관계를 알 수 있는 값이다. 예를 들면 다음과 같이 나타난다.

(임의로 대강 쓴 값이기 때문에 실제와는 다름..!)

여기서 hull의 시계방향으로 값을 읽어보면, [12, 6, 3, 9, 15, 18]이다.

잘 생각해보면 이 값 중 최솟값 및 최댓값을 가지는 점에서 이 hull은 그 직선과 접한다. 즉 세 번째 점(값이 3으로 최소)에서 위쪽에서 접하고, 여섯 번째 점(값이 18로 최대)에서 아래쪽에서 접한다. 아까 구하고자 했던 것이 이 접점이었다.

지금 하고자 하는 주장은, 바로 이 값이 3분 탐색이 가능하다는 것! 즉 꾸준히 감소-최솟값-꾸준히 증가 혹은 꾸준히 증가-최댓값-꾸준히 감소의 꼴을 띈다는 것이다. 이는 잘 생각해보면 증명할 수 있다. 쉽게 하는 방법은, 전체 평면을 돌려 지금 보고 있는 기울기가 x축과 평행하게 되도록 놓고 본다. 그러면 hull은 적당히 돌아간 활 모양으로 되어있으며, 시계/반시계 방향으로 훑어보면 y좌표(돌린 후)는 한 번 내려갔다가 올라가고 멈추거나 그 반대이다. 그렇지 않으면 hull이 반쪽짜리, 즉 기울기가 최대 π만큼 변한다는 가정에 어긋난다.

단 '꾸준히' 부분에서는 기울기가 0인 부분도 있을 수 있다. 즉 [5, 5, 3, 4, 8] 혹은 [1, 1, 2, 3, 5, 8, 8]의 모양도 가능하다는 것. 하지만 이런 꼴의 배열에서도 여전히 삼분탐색은 가능하다.

각각의 hull에 대해 방향을 고려하며 처리하기가 매우 귀찮기 때문에, 각각의 hull을 아래로 볼록하다고 보고 한 번, 위로 볼록하다고 보고 한 번 돌려버리면 깔끔하다. 어차피 두 번 중 한 번은 제대로 걸리게 되어있다.

 
xxxxxxxxxx
pair<ll,pii> tri(vector<pii>& h, int a, int b, int maxmin, ll init_val){
    int n=h.size();
    auto f=[&](int i){
      return make_pair(h[i].x*1LL*a + h[i].y*1LL*b, h[i]);
    };
    pair<ll,pii> ret = {init_val, {0, 0}};
  
    // tri-search, v-shaped
    int l=0, r=n-1;
    while(l+3 < r){
        int p1=(l*2+r)/3, p2=(l+2*r)/3;
        if(f(p1) > f(p2)) l=p1; else r=p2;
    }
    for(int i=l; i<=r; ++i) ret=(ret>f(i) == maxmin ? ret:f(i));
  
    // tri-search, ^-shaped
    l=0, r=n-1;
    while(l+3 < r){
        int p1=(l*2+r)/3, p2=(l+2*r)/3;
        if(f(p1) < f(p2)) l=p1; else r=p2;
    }
    for(int i=l; i<=r; ++i) ret=(ret>f(i) == maxmin ? ret:f(i));
  
    return ret;
}
​
ll tan_up_val; pii tan_up;
tie(tan_up_val, tan_up) = max(tri(uh, a, b, 1, -inf), tri(dh, a, b, 1, -inf));
ll tan_down_val; pii tan_down;
tie(tan_down_val, tan_down) = min(tri(uh, a, b, 0, inf), tri(dh, a, b, 0, inf));

Convex Hull 밖의 점에서 Convex Hull에 그은 접선

일단 점 P에서 convex hull C에 접선을 긋는다고 하자.

생각해볼 것은, P를 기준으로 C의 각 점이 위치하는 각도이다. 잘 생각해보면 이 각도는 일정 범위를 가질 것이고, 그 범위의 양 끝이 바로 접선이 될 것이다. 이 범위는 절대 π를 넘지 못한다. π를 넘으면 C가 convex하지 않든가 P가 C의 내부에 있다.

그렇다면 무식한 방법. 지금까지 나온 것중 가장 clockwise한 것과 counter-clockwise한 것을 놓고, C의 각 점에 대해서 P와 직선을 그어보며 이를 ccw()를 써서 갱신한다. 시간은 $O(\|C\|)$. 범위가 π를 넘는다면 ccw()를 할 때 벡터가 반대쪽으로 넘어가 엄한 결과가 나와버리기 때문에, π를 넘지 않는다는 가정이 꼭 필요한 것이다.

물론 우리는 알고 있다. 뭘? 이걸 $O(log\|C\|)$에 할 수 있다는걸! 역시 이분탐색을 잘... 하면 될 것 같지만 역시 귀찮다ㅜㅜ

근데 여기서 또 하나. 그 각도 역시 위와 마찬가지로 삼분탐색이 가능하다!!

 
xxxxxxxxxx
pair<pii,pii> tri(vector<pii>& h, pii orig, int maxmin){
    int n=h.size();
    auto f=[&](int i){
        return make_pair(h[i]-orig, h[i]);
    };
    pair<pii,pii> ret = f(0);
  
    // tri-search, v-shaped
    int l=0, r=n-1;
    while(l+3 < r){
        int p1=(l*2+r)/3, p2=(l+2*r)/3;
        if(ccw(f(p1).first, f(p2).first)) l=p1; else r=p2;
    }
    for(int i=l; i<=r; ++i) ret=(ccw(ret.first, f(i).first) == maxmin ? f(i):ret);
  
    // tri-search, ^-shaped
    l=0, r=n-1;
    while(l+3 < r){
        int p1=(l*2+r)/3, p2=(l+2*r)/3;
        if(!ccw(f(p1).first, f(p2).first)) l=p1; else r=p2;
    }
    for(int i=l; i<=r; ++i) ret=(ccw(ret.first, f(i).first) == maxmin ? f(i):ret);
  
    return ret;
}
​
auto ccw_comp = [](const pair<pii,pii>& a, const pair<pii,pii>& b){
    return ccw(a.x, b.x);
};
pii tan_up_val; pii tan_up;
tie(tan_up_val, tan_up) = max(tri(uh, orig, 1), tri(dh, orig, 1), ccw_comp);
pii tan_down_val; pii tan_down;
tie(tan_down_val, tan_down) = min(tri(uh, orig, 0), tri(dh, orig, 0), ccw_comp);