解題區/出題解題

[ACM 題目] 竹馬不敵天降

contents

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

Problem

「話說，剛剛明明說的是合乎聖誕節的商品。這不是 H-GAME 嗎？哪裡有聖誕元素啊！」
「嗯，真虧你發現這點啊，但還是有點可惜，這是全齡版，沒有工口哦！」
「不管怎麼樣，一點也沒合聖誕節啊。」
「雖然你有好好學習許多東西，但對本質上完全沒有理解。」
「最近開始覺得有點明白了 …」
「那麼就來說明下這個作品吧」
「是一年前發售的大人氣美少女遊戲的續篇吧？」
「是的，那為什麼你沒有察覺到－『一年前』這句話所包含的意義」
「對於期盼著的人那就意味著 … 與戀人時隔一年的再會！」

在 GALGAME 故事發展過程中，竹馬幾乎沒勝過天降，走哪一條線進行發展正是玩 GALGAME 的樂趣。

然而有一款極為糟糕的 GALGAME 的初始方式則是在一開始選定座標下，系統會根據座標找到附近最鄰近少女，並且在隨後的故事情節都會圍繞這名少女。

遊戲的地圖設計很簡單，用一個矩形表示，現在已知 N 名少女的所在地 (都在矩形內部)。一開始選定的座標也必須落在矩形內，請問玩哪每個線路機率分布為何？

Input

輸入有多組測資。

每組第一行會有三個整數 N, A, B，表示在$[0:A] \times [0:B]$ 地圖中有 N 個已知座標。
接下來會有 N 行，每行上會有兩個整數 x, y，表示每名少女所在的座標$(x, y)$ 保證不會有重疊的情況。

$(0 < N \le 100, 0 < A, B \le 1000, 0 \le x \le A, 0 \le y \le B)$

Output

對於每組測資輸出一行，根據輸入順序輸出每一個故事線的機率。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
2 5 3
1 2
4 2
  
2 5 3
1 1
2 2
  
3 5 3
1 1
2 2
4 1

Sample Output

1
2
3
Case 1: 0.500 0.500
Case 2: 0.300 0.700
Case 3: 0.292 0.313 0.396

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
#include <stdio.h> 
#include <math.h>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
#define eps 1e-6 
#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);
    }
    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;
}
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) {
    double a1, b1, c1, a2, b2, c2;
    double dx, dy, d;
    a1 = a.s.y - a.e.y, b1 = a.e.x - a.s.x;
    c1 = a1 * a.s.x + b1 * a.s.y;
    a2 = b.s.y - b.e.y, b2 = b.e.x - b.s.x;
    c2 = a2 * b.s.x + b2 * b.s.y;
    dx = c1 * b2 - c2 * b1, dy = a1 * c2 - a2 * c1;
    d = a1 * b2 - a2 * b1;
    return Pt(dx/d, dy/d);
}
Seg deq[MAXN];
vector<Pt> halfPlaneIntersect(vector<Seg> segs) {
    sort(segs.begin(), segs.end());
    int n = segs.size(), m = 1;
    int front = 0, rear = -1;
    for (int i = 1; i < n; i++) {
        if (fabs(segs[i].angle - segs[m-1].angle) > eps)
            segs[m++] = segs[i];
    }
    n = m;
    deq[++rear] = segs[0];
    deq[++rear] = segs[1];
    for (int i = 2; i < n; i++) {
        while (front < rear && cross(segs[i].s, segs[i].e, getIntersect(deq[rear], deq[rear-1])) < -eps)
            rear--;
        while (front < rear && cross(segs[i].s, segs[i].e, getIntersect(deq[front], deq[front+1])) < -eps)
            front++;
        deq[++rear] = segs[i];
    }
    while (front < rear && cross(deq[front].s, deq[front].e, getIntersect(deq[rear], deq[rear-1])) < -eps)
        rear--;  
    while (front < rear && cross(deq[rear].s, deq[rear].e, getIntersect(deq[front], deq[front+1])) < -eps)
    	front++;
    	
    vector<Pt> ret;
    for (int i = front; i < rear; i++) {
        Pt p = getIntersect(deq[i], deq[i+1]);
        ret.push_back(p);
    }
    if (rear > front + 1) {
        Pt p = getIntersect(deq[front], deq[rear]);
        ret.push_back(p);
    } 
    return ret;
}
double calc_convexarea(const vector<Pt> &p) {
    double ret = 0;
    int n = p.size();
    for(int i = 0, j = n - 1; i < n; j = i++)
        ret += p[j].x * p[i].y - p[j].y * p[i].x;
    return fabs(ret /2.0);
}
int main() {
    int n, A, B, cases = 0;
    Pt p[128], mid, vij;
    while (scanf("%d %d %d", &n, &A, &B) == 3) {
        for (int i = 0; i < n; i++)
            scanf("%lf %lf", &p[i].x, &p[i].y);
        printf("Case %d:", ++cases);
        for (int i = 0; i < n; i++) {
            int m = 0;
            vector<Seg> segs;
            segs.resize(n - 1 + 4);
            for (int j = 0; j < n; j++) {
                if (i == j)	continue;
                mid.x = (p[i].x + p[j].x) /2.0;
                mid.y = (p[i].y + p[j].y) /2.0;
                vij.x = mid.x - (p[j].y - p[i].y);
                vij.y = mid.y + (p[j].x - p[i].x);
                segs[m] = Seg(mid, vij), m++;
            }
            segs[m++] = Seg(Pt(0, 0), Pt(A, 0));
            segs[m++] = Seg(Pt(A, 0), Pt(A, B));
            segs[m++] = Seg(Pt(A, B), Pt(0, B));
            segs[m++] = Seg(Pt(0, B), Pt(0, 0));
            vector<Pt> convex = halfPlaneIntersect(segs);
//			for (int j = 0; j < convex.size(); j++)
//				printf("%lf %lf\n", convex[j].x, convex[j].y);
//			puts("--");
            printf(" %.3lf", calc_convexarea(convex) / (A * B));
        }
        puts("");
    }
    return 0;
}
/*
2 5 3
1 2
4 2
2 5 3
1 1
2 2
3 5 3
1 1
2 2
4 1
*/