Adding Points in a Half Convex Hull

Half Convex Hull

 문자 그대로 반껍질이다. 볼록 껍질을 구할 때처럼 하면 된다.

 

 BOJ 14745 - Jeong Lab

 문제를 다르게 바꾸면 다음과 같다.

 

 용액을 하나의 좌표로 보고, 점 \(Q(c_i, d_i)\)가 반껍질 내에 존재하는 지의 여부를 확인하기.

이 반껍질의 아래 영역에 점이 들어오는지 확인하면 된다.

 이는 매우매우 간단하다. lower_bound를 사용하여, 점 \(P_{l}, P_{l+1}, Q(c_i, d_i)\)의 ccw를 확인해주면 된다.

 

반껍질에 점 추가하기

 그러나 이 문제에서 요구하는 것이 하나 더 있다. 반껍질 내에 점이 존재하지 않는다면, 이 반껍질에 점을 추가해주어야 한다. 그리고 반껍질을 다시 구성해야 한다.

 

 먼저, 점이 들어갈 위치를 구한다. lower_bound를 사용하여 위치를 찾을 수 있다.

 그 다음, 한 쪽으로 쭉 진행하며 ccw를 확인하는데, 볼록 껍질을 구할 때와 같이, ccw 방향이 반대라면 점을 빼면 된다.

 반대쪽으로도 똑같이 진행하면 된다.

 

 점들을 빼주고, 추가하는 것을 빠르게 하기 위해 set을 사용하면 된다. 게다가 점의 삭제는 최대 \(O(N)\) 번 이루어지기 때문에, 전체 시간복잡도 \(O(NlgN)\)에 해결할 수 있다.

 

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

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <tuple>
 
#define all(v) v.begin(),v.end()
using namespace std;
using ll = long long;
using ld = long double;
 
typedef pair<ld, ld> pdd;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
#define X first
#define Y second
#define endl '\n'
 
 
set<pii> st;
 
 
ll ccw(pii a, pii b, pii c) {
    return (ll)a.X * b.Y + (ll)b.X * c.Y + (ll)c.X * a.Y - (ll)a.Y * b.X - (ll)b.Y * c.X - (ll)c.Y * a.X;
}
 
bool isIn(int x, int y) {
    auto l = st.lower_bound({ x, -1 });
    if (l == st.end()) return false;
    if (l == st.begin()) return l->Y >= y;
    auto r = l--;
    return ccw(*l, { x, y }, *r) >= 0;
}
 
void insertPoint(int x, int y) {
    if (isIn(x, y)) return;
    auto it = st.insert({ x, y }).X;
    if (it != st.begin()) {
        auto l = it, r = --l;
        while (r != st.begin()) {
            r--;
            if (ccw(*r, *l, *it) >= 0) {
                st.erase(l);
                l = r;
            }
            else break;
        }
        while (it != st.begin()) {
            l = it; l--;
            if (l->Y <= y) st.erase(l);
            else break;
        }
    }
    if (it != st.end()) {
        auto l = it, r = ++l;
        while (r != st.end()) {
            r++;
            if (r == st.end()) break;
            if (ccw(*it, *l, *r) >= 0) {
                st.erase(l);
                l = r;
            }
            else break;
        }
    }
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n; cin >> n;
 
    for (int i = 0; i < n; i++) {
        int x, y; cin >> x >> y;
        insertPoint(x, y);
    }
 
    int m; cin >> m;
    for (int i = 0; i < m; i++) {
        int x, y; cin >> x >> y;
        if (!isIn(x, y)) {
            cout << "Yes" << endl;
            insertPoint(x, y);
        }
        else {
            cout << "No" << endl;
        }
    }
    
 
    return 0;
}

 

 

 이것을 응용하여 반껍질이 아닌, 볼록 껍질에 점 추가를 할 수도 있다. 근데 이건 아직 안 해봤고.. 자신이 없다.

 

 BOJ 23272 - Hiring Help

 점 삭제는 힘들어 보이니, 쿼리를 뒤집어서 점 추가로 바꾸어 풀면 된다.