解題區/解題區 - UVa

UVa 1475 - Jungle Outpost

contents

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

Problem

有一個軍事基地在叢林深處隱藏，基地將會由 n 個塔台包圍保護。並且只能保護其凸包內的所有地區。

敵人可以摧毀一些塔，使得保護區的保護範圍縮小，使得基地給暴露出來。

在萬無一失的條件下，希望將基地建造在敵人需要摧毀最多塔台才能基地所在地。

Sample Input

1
2
3
4
5
6
7
8
9
10
3 
0 0 
50 50 
60 10 
5 
0 0 
0 10 
10 20 
20 10 
25 0

Sample Output

1
2
1
2

Solution

二分需要摧毀的塔台數 K，由於敵人最多摧毀 K 個塔台，就能將基地給找出來，也就是說任意炸掉連續區段的塔台，他們所產生出來的交集是存在的。如果沒有存在交集，則基地可以藏在那裏面，不管敵人怎麼摧毀都找不到基地在哪。

為什麼需要連續呢？分段結果肯定不好，涵蓋的面積也少，同時會被連續 K 的情況給包含，所以不用考慮分段。

N 很大，半平面交的誤差也很大。

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 <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 {
        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);
}
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;
}
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;
}
Seg deq[MAXN];
int 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++;
    return front + 1 < rear;
//    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;
}
int testBlowUp(int m, Pt D[], int n) {
    vector<Seg> segs;
    for (int i = 0; i < n; i++) {
        Pt a = D[i], b = D[i + m];
        segs.push_back(Seg(b, a));
    }
    return halfPlaneIntersect(segs);
}
Pt D[131072];
int main() {
    int n;
    while (scanf("%d", &n) == 1 && n) {
        for (int i = 0; i < n; i++) {
            scanf("%lf %lf", &D[i].x, &D[i].y);
            D[i + n] = D[i];
        }
        if (n <= 3) {
            puts("1");
            continue;
        }
        int l = 1, r = n - 2, mid, ret;
        while (l <= r) {
            mid = (l + r)/2;
            if(testBlowUp(mid, D, n))
                l = mid + 1, ret = mid;
            else
                r = mid - 1;
        }
        printf("%d\n", ret);
    }
    return 0;
}
/*
3 
0 0 
50 50 
60 10 
5 
0 0 
0 10 
10 20 
20 10 
25 0
*/