解題區/解題區 - UVa

UVa 10867 - Cutting a Polygon

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
13
14
15
16
9 5
0 0
0 2
1 1
2 2
3 1
4 2
5 1
6 2
6 0
-1 2 7.5 1
0 1 6 1
0 1.5 6 1.5
0 2 6 1
0 0 0 2
0 0

Sample Output

1
2
3
4
5
2.798
6.000
3.000
2.954
2.000

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
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
#include <stdio.h> 
#include <math.h>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
#define eps 1e-9
#define MAXN 131072
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 {
    	return fabs(x - a.x) < eps && fabs(y - a.y) < eps;
    }
    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 length() {
        return hypot(x, y);
    }
};
double dist(Pt a, Pt b) {
    return (a-b).length();
}
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 intersection(Pt as, Pt at, Pt bs, Pt bt) {
    if (cross(as, at, bs) * cross(as, at, bt) < -eps &&
        cross(at, as, bs) * cross(at, as, bt) < -eps &&
        cross(bs, bt, as) * cross(bs, bt, at) < -eps &&
        cross(bt, bs, as) * cross(bt, bs, at) < -eps)
        return 1;
    return 0;
}
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;
    }
};
Pt getIntersect(Seg a, Seg b) {
    Pt u = a.s - b.s;
    double t = cross2(b.e - b.s, u)/cross2(a.e - a.s, b.e - b.s);
    return a.s + (a.e - a.s) * t;
}
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;
}
double solve(Pt D[], int n, Pt s, Pt e) {
    vector<Pt> p;
    for (int i = 0, j = n - 1; i < n; j = i++) {
        if (cross(s, e, D[i]) * cross(s, e, D[j]) < -eps) {
            Pt t = getIntersect(Seg(D[i], D[j]), Seg(s, e));
            p.push_back(t);
        } else if (onSeg(s, e, D[i]) || fabs(cross(s, e, D[i])) < eps)
            p.push_back(D[i]);
    }
    p.push_back(s);
    p.push_back(e);
    sort(p.begin(), p.end());
    double ret = 0;
    for (int i = 0; i + 1 < p.size(); i++) {
        Pt mid = (p[i] + p[i+1]) * 0.5;
        if (inPolygon(D, n, mid))
            ret += dist(p[i], p[i+1]);
//		printf("%lf %lf ++++\n", p[i].x, p[i].y);
    }
    return ret;
}
int main() {
    int n, m;
    while (scanf("%d %d", &n, &m) == 2 && n) {
        Pt D[2048];
        for (int i = 0; i < n; i++)
            scanf("%lf %lf", &D[i].x, &D[i].y);
        Pt s, e;
        for (int i = 0; i < m; i++) {
            scanf("%lf %lf", &s.x, &s.y);
            scanf("%lf %lf", &e.x, &e.y);
            double ret = solve(D, n, s, e);
            printf("%.3f\n", ret);
        }
    }
    return 0;
}
/*
9 5
0 0
0 2
1 1
2 2
3 1
4 2
5 1
6 2
6 0
-1 2 7.5 1
0 1 6 1
0 1.5 6 1.5
0 2 6 1
0 0 0 2
4 9
0 0 
0 1
1 1
1 0
0 0 1 1
1 1 0 0
0 0 1 0
0 0 0.5 0
0 0.5 1 0.5
0 1 1 1
1 1 1 0
0.75 0.75 0.75 0.25
0 0.25 1 0.75
*/