解題區/出題解題

[ACM 題目] 單調測試

contents

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

Problem

單調－這性質相當巧妙，可以在算法上好好地敲上一筆，處理速度跟你輸入的速度一樣快呢。

Background

這是計算幾何作業中的一環，但是找到一個 O(n) 算法果然不容易。

3.11 Give an efficient algorithm to determine whether a polygon P with n vertices is monotone with respect to some line, not necessarily a horizontal or vertical one.

到底有沒有可能用單調性質測試單調呢？ O(n log n) 就是極限？讓我們來挑戰挑戰。

Problem

假想一個二維平面，x 軸左右兩側將會射入雷射，現在要將一個簡單多邊形由上往下放入，雷射將會打在第一個碰觸的點上，請問有沒有一種放置方式，使得每一個邊都被雷射覆蓋到。

山形

如上圖，假使這樣放置，位置 (0, 0), (2, 0) 將無法被雷射覆蓋，如果將此圖旋轉 90 度放入，就能覆蓋到所有邊了！因此，決定是否有一個角度放入，能覆蓋到所有邊。

Input

有多組測資，每一組測資第一行將會有一個整數 N，

接下來會有 N 行，每一行上會有一個座標 (x, y)，採用順時針或者逆時針順序。

Output

對於每組測資輸出一行，每一行輸出 yes/no。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
8
-2 0
1 -1
4 0
3 2
2 0
1 3
0 0
-1 2
8
1 2
2 2
2 3
-1 3
-1 -2
2 -2
2 -1
1 -1

Sample Output

1
2
yes
no

Solution

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
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <string.h>
#include <assert.h>
#include <map>
using namespace std;
#define eps 1e-10
#define MAXN 32767
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 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;
    }
};
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);
}
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;
}
Pt getIntersect(Pt l1, Pt p1, Pt l2, Pt p2) {
    double a1, b1, c1, a2, b2, c2;
    double dx, dy, d;
    a1 = l1.y, b1 = -l1.x;
    c1 = a1 * p1.x + b1 * p1.y;
    a2 = l2.y, b2 = -l2.x;
    c2 = a2 * p2.x + b2 * p2.y;
    dx = c1 * b2 - c2 * b1, dy = a1 * c2 - a2 * c1;
    d = a1 * b2 - a2 * b1;
    return Pt(dx/d, dy/d);
}
struct Seg {
    Pt s, e;
    double angle;
    int label;
    Seg(Pt a = Pt(), Pt b = Pt(), int l=0):s(a), e(b), label(l) {
        angle = atan2(e.y - s.y, e.x - s.x);
    }
    bool operator<(const Seg &other) const {
        if (fabs(angle - other.angle) > eps)
            return angle > other.angle;
        if (cross(other.s, other.e, s) > -eps)
            return true;
        return false;
    }
};
struct CMP2 {
    bool operator()(const double &i, const double &j) const {
        if (fabs(i-j) > eps)
            return i < j;
        return false;
    }
};
Seg segs[MAXN];
Pt D[MAXN];
int testMonotone(int n, Pt D[]) {
    int m = 0, origin_n = n;
    D[n] = D[0], D[n+1] = D[1];
    for (int i = 1; i <= n; i++) {
        Pt v1 = D[i + 1] - D[i];
        Pt v2 = D[i - 1] - D[i];
        segs[m++] = Seg(v1, v2, i);
        segs[m++] = Seg(v1 * -1, v2 * -1, i);
    }
    n = m;
    Pt pos = Pt(0, 0);
    set<int> S;
    map<double, vector< pair<int, int> >, CMP2> angle;
    for (int i = 0; i < n; i++) {
        double v1 = atan2(segs[i].s.y - pos.y, segs[i].s.x - pos.x);
        double v2 = atan2(segs[i].e.y - pos.y, segs[i].e.x - pos.x);
        angle[v1].push_back(make_pair(i, 0));
        angle[v2].push_back(make_pair(i, 1));
    }
    double c;
    pair<int, int> u = angle.begin()->second[0];
    Pt fpt;
    if (u.second == 0)  fpt = segs[u.first].s;
    else                fpt = segs[u.first].e;
    for (int i = 0; i < n; i++) {
        if (cross(pos, fpt, segs[i].s) * cross(pos, fpt, segs[i].e) < 0) {
            Pt q = getIntersect(segs[i].s - segs[i].e, segs[i].s, fpt - pos, pos);
            if (dot(q - pos, fpt - pos) > 0)
                S.insert(segs[i].label);
        } 
    }
    for (map<double, vector< pair<int, int> >, CMP2>::iterator it = angle.begin();
         it != angle.end(); it++) {
        for (int i = 0; i < it->second.size(); i++) {
            pair<int, int> u = it->second[i];
            if (u.second == 0)
                c = cross(pos, segs[u.first].s, segs[u.first].e);
            else
                c = cross(pos, segs[u.first].e, segs[u.first].s);
            if (fabs(c) > eps) {
                if (c > 0)
                    S.insert(segs[u.first].label);
                else
                    S.erase(segs[u.first].label);
            }
        }
        if (S.size() >= origin_n - 2)
            return 1;
    }
    return 0;
}
int main() {
    int n;
    double x, y;
    while (scanf("%d", &n) == 1) {
        for (int i = 0; i < n; i++) {
            scanf("%lf %lf", &x, &y);
            D[i] = Pt(x, y);
        }
        int flag = testMonotone(n, D);
        puts(flag ? "yes" : "no");
    }
    return 0;
}