解題區/解題區 - UVa

UVa 881 - Points, Polygons and Containers

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

有數個不相交的簡單多變形，構成類似等高線的地勢圖，每一個簡單多邊形都有其代碼編號，接著有數個不按照順序的詢問點，請問所在的位置是在哪一塊。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
1
4
3 18 16 1 16 1 1 18 1
1 2 15 2 2 14 2
4 15 2 15 15 3 15
2 10 4 4 10 4 4
4
2 20 4
4 3 11
3 5 6
1 12 11

Sample Output

1
2
3
4
1 4
2 0
3 2
4 1

Solution

首先用射線法，找到所有的簡單多邊形關係，O(n^2) 找到 DAG 圖。

接著將 DAG 圖縮成一個 rooted tree 圖，挑選深度最深的節點，外圍的深度是 0，越靠近裡面深度越高。

接著對於每一組詢問，從 root 開始走訪，直到沒有可以包含住這個點。

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
#include <stdio.h> 
#include <math.h>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <iostream>
#include <assert.h>
using namespace std;
#define eps 1e-8
#define MAXN 1024
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}	
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    Pt operator*(const double a) const {
        return Pt(x * a, y * a);
    }
    bool operator<(const Pt &a) const {
        if (fabs(x - a.x) > eps)
            return x < a.x;
        if (fabs(y - a.y) > eps)
            return y < a.y;
        return false;
    }
    bool operator==(const Pt &a) const {
        return fabs(x - a.x) < eps && fabs(y - a.y) < eps;
    } 
};
double dist(Pt a, Pt b) {
    return hypot(a.x - b.x, a.y - b.y);
}
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
double cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
int between(Pt a, Pt b, Pt c) {
    return dot(c - a, b - a) >= -eps && dot(c - b, a - b) >= -eps;
}
int onSeg(Pt a, Pt b, Pt c) {
    return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
int inPolygon(Pt p[], int n, Pt q) {
    int i, j, cnt = 0;
    for(i = 0, j = n-1; i < n; j = i++) {
        if(onSeg(p[i], p[j], q))
            return 1;
        if(p[i].y > q.y != p[j].y > q.y &&
            q.x < (p[j].x-p[i].x)*(q.y-p[i].y)/(p[j].y-p[i].y) + p[i].x)
            cnt++;
    }
    return cnt&1;
}
const double pi = acos(-1);
Pt polygon[MAXN][512];
int pn[MAXN], parent[MAXN], visited[MAXN], depth[MAXN];
int pid[MAXN];
vector<int> g[MAXN], tree[MAXN];
void dfs(int u) {
    visited[u] = 1, depth[u] = 0, parent[u] = -1;
    int d = -1;
    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (visited[v] == 0)	dfs(v);
        if (depth[v] > d)
            d = depth[v], parent[u] = v;
    }
    depth[u] = d + 1;
}
int query(int u, Pt q) {
    for (int i = 0; i < tree[u].size(); i++) {
        int v = tree[u][i];
        if (inPolygon(polygon[v], pn[v], q)) {
            return query(v, q);
        }
    }
    return u;
}
int main() {
    int testcase, n, m;
    string line;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        assert(n < MAXN);
        while (getchar() != '\n');
        for (int i = 0; i < n; i++) {
            getline(cin, line);
            stringstream sin(line);
            int m = 0;
            sin >> pid[i];
            while (sin >> polygon[i][m].x >> polygon[i][m].y) {
                m++;
                assert(m < 512);
            }
            pn[i] = m;
        }
        pid[n] = 0;
        for (int i = 0; i <= n; i++)
            g[i].clear(), visited[i] = 0, tree[i].clear();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j)	continue;
                if (inPolygon(polygon[i], pn[i], polygon[j][0]))
                    g[j].push_back(i);
            }
        }
        
        for (int i = 0; i < n; i++) {
            if (visited[i] == 0)
                dfs(i);
        }
        for (int i = 0; i < n; i++)
            if (parent[i] == -1)
                tree[n].push_back(i);
            else
                tree[parent[i]].push_back(i);
//		for (int i = 0; i < n; i++)
//			printf("%d: %d\n", pid[i], parent[i]);
        scanf("%d", &m);
        assert(m < 32767);
        int out[32767] = {};
        for (int i = 0; i < m; i++) {
            Pt q;
            int id;
            scanf("%d %lf %lf", &id, &q.x, &q.y);
            assert(id <= m);
            out[id] = query(n, q);
        }
        for (int i = 1; i <= m; i++)
            printf("%d %d\n", i, pid[out[i]]);
        if (testcase)
            puts("");
    }
    return 0;
}
/*
5
0 0
50 50
100 0
100 100
0 100
2
49 50
50 51
7
0 5
5 0
10 7
15 0
20 5
15 10
5 10
7
0 5
5 0
10 7
15 0
20 5
15 10
5 10
*/