解題區/解題區 - UVa

UVa 11106 - Rectilinear Polygon

contents

  1. 1. Problem
  2. 2. Sample input
  3. 3. Output for sample input
  4. 4. Solution

Problem

Given is n points with integer coordinates in the plane. Is it is possible to construct a simple, that is non-intersecting, rectilinear polygon with the given points as vertices? In a rectilinear polygon there are at least 4 vertices and every edge is either horizontal or vertical; each vertex is an endpoint of exactly one horizontal edge and one vertical edge. There are no holes in a polygon.

The first line of input is an integer giving the number of cases that follow. The input of each case starts with an integer 4 ≤ n ≤ 100000 giving the number of points for this test case. It is followed by n pairs of integers specifying the x and y coordinates of the points for this case.

The output should contain one line for each case on input. Each line should contain one integer number giving the length of the rectilinear polygon passing throught the given points when it exists; otherwise, it should contain -1.

Sample input

1
2
3
4
5
6
7
8
9
10
1
8
1 2
1 0
2 1
2 2
3 2
3 1
4 0
4 2

Output for sample input

1
12

Solution

題目描述：

給 N 個整數點座標，是否能構成一個直角的簡單多邊形，並請每個點都要在直角上。如果可以構成簡單多邊形，則輸出其多邊形周長為何。

題目解法：

由於每個點都必須在直角上，所以先考慮對 x = k 這一條直線上有數個點，則為了要構成簡單多邊形，保證這數個點根據 y 值排序，一定會構成 (y1, y2) (y3, y4) … 的連線，不然弄不出每一個點都在直角上。同理對於 y = k 考慮連線情況。

當我們將所有連線情況都記錄下後，要確保所有線段之間不會相交 (端點不算在相交情況中)，同時經過遍歷走訪後，所有的點都在同一個 component 上。

對於 N 個線段，可以在 O(N log N) 時間內得到是否有相交情況。代碼修改於 DJWS 演算法筆記

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
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
#include <stdio.h>
#include <stdio.h> 
#include <math.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
#define eps 1e-6
struct Pt {
    int x, y, label;
    Pt(int a = 0, int b = 0, int c = 0):
    	x(a), y(b), label(c) {}
    bool operator<(const Pt &a) const {
        if(x != a.x)	return x < a.x;
        return y < a.y;
    }
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
};
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 cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
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);
}
int between(Pt a, Pt b, Pt c) {
    return dot(c - a, b - a) >= 0 && dot(c - b, a - b) >= 0;
}
int onSeg(Pt a, Pt b, Pt c) {
    return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
int intersection(Pt as, Pt at, Pt bs, Pt bt) {
    if(cross(as, at, bs) * cross(as, at, bt) < 0 &&
       cross(at, as, bs) * cross(at, as, bt) < 0 &&
       cross(bs, bt, as) * cross(bs, bt, at) < 0 &&
       cross(bt, bs, as) * cross(bt, bs, at) < 0)
        return 1;
    return 0;
}
int cmpX(Pt a, Pt b) {
    if(a.x != b.x)	return a.x < b.x;
    return a.y < b.y;
}
int cmpY(Pt a, Pt b) {
    if(a.y != b.y)	return a.y < b.y;
    return a.x < b.x;
}
vector<int> g[100005];
int visited[100005], dfsCnt;
void dfs(int u, int p) {
    visited[u] = 1, dfsCnt++;
    for(int i = g[u].size()-1; i >= 0; i--) {
        int v = g[u][i];
        if(v == p || visited[v])	continue;
        dfs(v, u);
    }
}
// http://www.csie.ntnu.edu.tw/~u91029/PointLinePlane2.html
struct seg {
    Pt s, e;
    seg(Pt a, Pt b):s(a), e(b) {}
};
struct Endpoint {
    int x, s, i;
    Endpoint(int a = 0, int b = 0, int c = 0):
        x(a), s(b), i(c) {}
    bool operator<(const Endpoint &a) const {
        return x < a.x || (x == a.x && s > a.s);
    }
};
struct CMP {
    static int x;
    
    double interpolate(const Pt& p1, const Pt& p2, int& x) {
        if (p1.x == p2.x) return p1.y;
        return p1.y + (double)(p2.y - p1.y) / (p2.x - p1.x) * (x - p1.x);
    }
    
    bool operator()(const seg &i, const seg &j) {
        return interpolate(i.s, i.e, x) < interpolate(j.s, j.e, x);
    }
};
int CMP::x = 0;
set<seg, CMP>::iterator prevNode(set<seg, CMP>::iterator it, set<seg, CMP>& S) {
    return it == S.begin() ? it : --it;
}
set<seg, CMP>::iterator nextNode(set<seg, CMP>::iterator it, set<seg, CMP>& S) {
    return it == S.end() ? it : ++it;
}
bool segment_intersect(vector<seg> segs) {
    for(int i = 0; i < segs.size(); i++)
        if(segs[i].e < segs[i].s)
            swap(segs[i].s, segs[i].e);
            
    vector<Endpoint> e;
    set<seg, CMP> S;
    for(int i = 0; i < segs.size(); i++) {
        e.push_back(Endpoint(segs[i].s.x, 1, i));
        e.push_back(Endpoint(segs[i].e.x, -1, i));
    }
    sort(e.begin(), e.end());
    
    for(int i = 0; i < e.size(); i++) {
        CMP::x = e[i].x;
        if(e[i].s == 1) {
            set<seg, CMP>::iterator it, jt;
            it = S.lower_bound(segs[e[i].i]);
            jt = prevNode(it, S);
            if(it != S.end() && intersection(segs[e[i].i].s, segs[e[i].i].e, it->s, it->e))
                return 1;
            if(jt != S.end() && intersection(segs[e[i].i].s, segs[e[i].i].e, jt->s, jt->e))
                return 1;
            S.insert(segs[e[i].i]);
        } else {
            set<seg, CMP>::iterator it, jt, kt;
            it = S.lower_bound(segs[e[i].i]);
            jt = prevNode(it, S);
            kt = nextNode(it, S);
            if(jt != S.end() && kt != S.end() && intersection(kt->s, kt->e, jt->s, jt->e))
                return 1;
            if(it != S.end())
                S.erase(it);
        }
    } 
    return 0;
}
Pt D[100005], P[100005];
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
    
    int testcase, n;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d", &n);
        for(int i = 0; i < n; i++) {
            scanf("%d %d", &P[i].x, &P[i].y);
            D[i] = P[i], D[i].label = i;
        }
        
        int eflag = 0;
        for(int i = 0; i < n; i++)
            g[i].clear(), visited[i] = 0;
        sort(D, D+n, cmpX);		
        for(int i = 0; i < n && !eflag; i += 2) {
            if(i+1 < n && D[i].x == D[i+1].x) {
                g[D[i].label].push_back(D[i+1].label);
                g[D[i+1].label].push_back(D[i].label);
            } else
                eflag = 1;
        }
        sort(D, D+n, cmpY);
        for(int i = 0; i < n && !eflag; i += 2) {
            if(i+1 < n && D[i].y == D[i+1].y) {
                g[D[i].label].push_back(D[i+1].label);
                g[D[i+1].label].push_back(D[i].label);
            } else
                eflag = 1;
        }
        
        if(!eflag) { // only one component
            dfsCnt = 0;
            dfs(0, -1);
            if(dfsCnt != n)
                eflag = 1;
        }
        
        if(!eflag) {
            vector<seg> segs;
            for(int i = 0; i < n; i++) {
                for(int j = g[i].size()-1; j >= 0; j--) {
                    segs.push_back(seg(P[i], P[g[i][j]]));
                }
            }
            eflag = segment_intersect(segs);
        }
        
        if(eflag)
            puts("-1");
        else {
            int para = 0;
            for(int i = 0; i < n; i++) {
                for(int j = g[i].size()-1; j >= 0; j--) {
                    para += abs(P[i].x - P[g[i][j]].x) + abs(P[i].y - P[g[i][j]].y);
                }
            }
            printf("%d\n", para/2);
        }
    }
    return 0;
}
/*
5
6
68 81
65 33
32 94
52 80
63 44
11 41
*/