백준5383 안녕! 난 루피! 장래에 해적왕이 될 사내다!

작성일 | In

문제 링크

  • https://icpc.me/5383

문제 출처

  • 2011 BAPC C번

사용 알고리즘

  • Point-Line Duality
  • Convex Hull

시간복잡도

  • $O((N+M) \log M)$

풀이

$T_l$이 $T_r$보다 왼쪽에 있다는 정보를 $T_l$과 $T_r$을 연결하는 직선으로 생각하면, 각 점이 Half Plane Intersection으로 구한 볼록 다각형 내부에 있는지 판별하는 문제가 됩니다. HPI를 짜는 것은 귀찮으므로 다른 풀이를 생각해 봅시다.

$x(T_l) < x(T_r)$이면 어떤 점 $P$가 정답이 위해서는 $T_l$과 $T_r$을 연결하는 직선 $L_1$보다 아래에 있어야 합니다. 반대로 $x(T_l) > x(T_r)$이면 $P$는 $T_l$과 $T_r$을 연결하는 직선 $L_2$보다 위에 있어야 합니다.
Point-Line Duality를 사용하면 점 $L_1^\ast$는 직선 $P^\ast$보다 아래에 있어야 하고, $L_2$는 $P^\ast$보다 위에 있어야 합니다. 이때 $P(a, b), L: y=ax+b$라고 하면 $P^\ast = ax-b, L^\ast(a, -b)$입니다.

따라서 이 문제는 $L_1^\ast$들의 upper hull보다 위에 있고 $L_2^\ast$들로 만든 lower hull보다 아래에 있는 $P^\ast$를 구하는 문제입니다. 위/아래 껍질은 $O(M \log M)$에 구할 수 있고, 기울기가 주어졌을 때 볼록 다각형의 접점을 $O(\log N)$ 시간에 구할 수 있으므로 전체 문제를 $O((N+M) \log M)$ 정도에 해결할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <bits/stdc++.h>
using namespace std;
using real_t = double;
constexpr real_t EPS = 1e-6;

struct Point{
    real_t x, y;
    Point() : Point(0, 0) {}
    Point(real_t x, real_t y) : x(x), y(y) {}
    bool operator < (const Point &p) const { return tie(x,y) < tie(p.x,p.y); }
};

real_t CCW(const Point &p1, const Point &p2, const Point &p3){
    return (p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y);
}

template<bool UPPER=true>
vector<Point> GetHull(vector<Point> points){
    vector<Point> res;
    sort(points.begin(), points.end());
    auto chk = [](Point a, Point b, Point c){ return CCW(a, b, c) * (UPPER ? 1 : -1) >= 0; };
    for(auto i : points){
        while(res.size() >= 2 && chk(res[res.size()-2], res.back(), i)) res.pop_back();
        res.push_back(i);
    }
    return res;
}

template<bool UPPER=true>
Point GetPoint(const vector<Point> &hull, real_t slope){
    auto chk = [slope](real_t dx, real_t dy){ return UPPER ? dy >= slope * dx : dy <= slope * dx; };
    int l = -1, r = hull.size() - 1;
    while(l + 1 < r){
        int m = (l + r) / 2;
        if(chk(hull[m+1].x - hull[m].x, hull[m+1].y - hull[m].y)) l = m; else r = m;
    }
    return hull[r];
}

Point GetLineToPoint(const Point &p1, const Point &p2){
    real_t a = (p2.y - p1.y) / (p2.x - p1.x);
    real_t b = a * p1.x - p1.y;
    return Point(a, b);
}

void Solve(){
    int N; cin >> N;
    vector<Point> P(N);
    for(auto &[x,y] : P) cin >> x >> y;

    int Q; cin >> Q;
    for(int q=0; q<Q; q++){
        int M; cin >> M;
        vector<Point> U, L;
        for(int i=0; i<M; i++){
            int u, v; cin >> u >> v; u--; v--;
            (P[u].x < P[v].x ? U : L).push_back(GetLineToPoint(P[u], P[v]));
        }
        U = GetHull<true>(U);
        L = GetHull<false>(L);

        for(int i=0; i<N; i++){
            real_t a = P[i].x, b = -P[i].y;
            if(!U.empty()){
                auto pt = GetPoint<true>(U, a);
                if(pt.x * a + b <= pt.y + EPS) continue;
            }
            if(!L.empty()){
                auto pt = GetPoint<false>(L, a);
                if(pt.x * a + b >= pt.y - EPS) continue;
            }
            cout << i + 1 << "\n";
        }
        cout << 0 << "\n";
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int TC; cin >> TC;
    for(int tc=1; tc<=TC; tc++) Solve();
}