A friend of yours has taken the job of security officer at the Star-Buy Company, a famous depart-
ment store. One of his tasks is to install a video surveillance system to guarantee the security of the
customers (and the security of the merchandise of course) on all of the store's countless floors. As the
company has only a limited budget, there will be only one camera on every floor. But these cameras
may turn around to look in every direction.
The first problem is to choose where to install the camera for every floor. The only requirement
is that every part of the room must be visible from there. In the following figure the left floor can be
completely surveyed from the position indicated by a dot, while for the right floor, there is no such
position, the given position failing to see the lower left part of the floor.
Before trying to install the cameras, your friend first wants to know whether there is indeed a
suitable position for them. He therefore asks you to write a program that, given a ground plan, de-
termines whether there is a position from which the whole floor is visible. All floor ground plans
form rectangular polygons, whose edges do not intersect each other and touch each other only at the
corners.
The input file contains several floor descriptions. Every description starts with the number n of vertices
that bound the floor (
). The next n lines contain two integers each, the x and y coordinates
for the n vertices, given in clockwise order. All vertices will be distinct and at corners of the polygon.
Thus the edges alternate between horizontal and vertical.
A zero value for n indicates the end of the input.
For every test case first output a line with the number of the floor, as shown in the sample output.
Then print a line stating ``Surveillance is possible.'' if there exists a position from which
the entire floor can be observed, or print ``Surveillance is impossible.'' if there is no such position.
Print a blank line after each test case.
4
0 0
0 1
1 1
1 0
8
0 0
0 2
1 2
1 1
2 1
2 2
3 2
3 0
0
Floor #1
Surveillance is possible.
Floor #2
Surveillance is impossible.
Miguel A. Revilla
1998-03-10
題目描述：詢問一個簡單多邊形是否存在可以放置一個監視器看到所有角落，
也就是問多邊形存不存在一個"核"。
題目解法：
凸多邊形不用講一定存在核！而簡單多邊形要判斷的話，
考慮看到一條牆壁，則可行解一定在其延長的其中一邊，對於所有牆壁查找交集可能。中間一定會用"半平面"去處理切割交集，現在的問題是，如何決策要取哪一邊？網路上提供了找凸凹什麼的做法，我看不是很懂。
題目給定的方式是順時針，因此決策哪一邊的時候，會拉兩點成為一直線去切半平面，
而對於下一個鄰近點時，這三個點會有一個三角形，查找邊上中間那個點有沒有在簡單多邊形中，
如果在的話，則選同一邊進行取捨。
因此判斷一個點有沒有在簡單多邊形內部時，使用射線法進行判斷。
半平面的做法只寫一個樸素的，沒有快速的 O(nlogn)。
特別注意到，題目問的是存不存在一個核，並不能用半平面的面積進去判斷。
即使解是一個點也算答案，判斷集合是否非空。
#include <stdio.h>
#include <math.h>
#include <algorithm>
#define DEBUG 0
using namespace std;
struct Pt {
double x, y;
Pt(double a=0, double b=0):
x(a), y(b) {}
bool operator !=(const Pt &a) const {
return fabs(x-a.x) > 1e-6 || fabs(y-a.y) > 1e-6;
}
bool operator ==(const Pt &a) const {
return fabs(x-a.x) < 1e-6 && fabs(y-a.y) < 1e-6;
}
};
struct Polygon {
Pt p[256];// clockwise
int n;
};
int inPolygon(Polygon p, Pt q) {
int i, j, cnt = 0;
for(i = 0, j = p.n-1; i < p.n; j = i++) {
if(p.p[i].y > q.y != p.p[j].y > q.y &&
q.x < (p.p[j].x-p.p[i].x)*(q.y-p.p[i].y)/(p.p[j].y-p.p[i].y)+p.p[i].x)
cnt++;
}
return cnt&1;
}
Polygon cutPolygon(double side, Polygon &p, Pt p1, Pt p2) {
// side : < 0 left, > 0 right, cut by lines(a, b)
int i, j, k;
double a, b, c;//ax + by + c = 0, pass {p1, p2}
Polygon A, B;// divide two or one set.
Pt intersection[2];// polygon divide by lines.
int cnt = 0;
a = p1.y - p2.y, b = p2.x - p1.x;
if(a < 0) a = -a, b = -b;
c = -(a*p1.x+b*p1.y);
p.p[p.n] = p.p[0];
A.n = B.n = 0;
for(i = 0; i < p.n; i++) {
if(cnt == 1) {
if(B.n == 0 || B.p[B.n-1] != p.p[i])
B.p[B.n++] = p.p[i];
} else {
if(A.n == 0 || A.p[A.n-1] != p.p[i])
A.p[A.n++] = p.p[i];
}
// segment&lines intersecion
if((a*p.p[i].x+b*p.p[i].y+c)*(a*p.p[i+1].x+b*p.p[i+1].y+c) < 1e-6) {
if(cnt == 2) continue;
double ta, tb, tc;
ta = p.p[i].y - p.p[i+1].y, tb = p.p[i+1].x - p.p[i].x;
tc = -(ta*p.p[i].x+tb*p.p[i].y);
double d, dx, dy;
d = a*tb-b*ta;
dx = (-c)*tb-b*(-tc), dy = a*(-tc)-(-c)*ta;
if(fabs(d) < 1e-6) {
continue;
//dx = p.p[i].x, dy = p.p[i].y;
} else {
dx /= d, dy /= d;
}
if(cnt == 1 && intersection[0] == Pt(dx, dy))
continue;
intersection[cnt++] = Pt(dx, dy);
if(A.n == 0 || A.p[A.n-1] != Pt(dx, dy))
A.p[A.n++] = Pt(dx, dy);
if(B.n == 0 || B.p[B.n-1] != Pt(dx, dy))
B.p[B.n++] = Pt(dx, dy);
}
}
while(A.n > 1 && A.p[0] == A.p[A.n-1])
A.n--;
while(B.n > 1 && B.p[0] == B.p[B.n-1])
B.n--;
#if DEBUG == 1
printf("%d %lf %lf\n", cnt, intersection[0].x, intersection[0].y);
puts("A -----");
for(i = 0; i < A.n; i++)
printf("(%lf %lf)\n", A.p[i].x, A.p[i].y);
puts("B -----");
for(i = 0; i < B.n; i++)
printf("(%lf %lf)\n", B.p[i].x, B.p[i].y);
#endif
if(A.n >= 2) {
double f;
for(i = 0; i < A.n; i++) {
f = a*A.p[i].x+b*A.p[i].y+c;
if(fabs(f) > 1e-6)
break;
}
if(i == A.n) return B;
//printf("fa %lf\n", f);
if((f < 0) == (side < 0))
return A;
else
return B;
} else {
double f;
for(i = 0; i < B.n; i++) {
f = a*B.p[i].x+b*B.p[i].y+c;
if(fabs(f) > 1e-6)
break;
}
if(i == B.n) return A;
//printf("fb %lf\n", f);
if((f < 0) == (side < 0))
return B;
else
return A;
}
}
int main() {
//freopen("video.in","r+t",stdin);
//freopen("out.txt","w+t",stdout);
int cases = 0;
int i, j, k;
Polygon in;
Polygon solution;
while(scanf("%d", &in.n) == 1 && in.n) {
for(i = 0; i < in.n; i++)// clockwise
scanf("%lf %lf", &in.p[i].x, &in.p[i].y);
solution.n = 4;
double lx, ly, rx, ry;
lx = rx = in.p[0].x;
ly = ry = in.p[0].y;
for(i = 0; i < in.n; i++) {
lx = min(lx, in.p[i].x);
ly = min(ly, in.p[i].y);
rx = max(rx, in.p[i].x);
ry = max(ry, in.p[i].y);
}
solution.p[0] = Pt(lx, ry);//left upper
solution.p[1] = Pt(rx, ry);//right upper
solution.p[2] = Pt(rx, ly);//right bottom
solution.p[3] = Pt(lx, ly);//left bottom
// solve
for(i = 0; i < in.n; i++) {// for each wall.
Pt p1 = in.p[i], p2 = in.p[(i+1)%in.n], p3 = in.p[(i+2)%in.n];
Pt mp = Pt((p1.x+p3.x)/2.0, (p1.y+p3.y)/2.0);
//printf("%lf %lf\n", mp.x, mp.y);
double a, b, c;//ax + by + c = 0, pass {p1, p2}
a = p1.y - p2.y, b = p2.x - p1.x;
if(a < 0) a = -a, b = -b;
c = -(a*p1.x+b*p1.y);
double side = a*mp.x+b*mp.y+c;
if(a*mp.x+b*mp.y+c < 0) {//left side
if(inPolygon(in, mp)) side = -1;
else side = 1;
} else {
if(inPolygon(in, mp)) side = 1;
else side = -1;
}
solution = cutPolygon(side, solution, p1, p2);
while(solution.n > 1 && solution.p[0] == solution.p[solution.n-1])
solution.n--;
if(solution.n == 0) break;
#if DEBUG == 1
printf("%lf x + %lf y + %lf = 0\n", a, b, c);
printf("%d- side %lf %lf %lf\n", solution.n, side, mp.x, mp.y);
for(j = 0; j < solution.n; j++)
printf("%lf %lf\n", solution.p[j].x, solution.p[j].y);
printf("########################### %d\n", i);
getchar();
#endif
}
printf("Floor #%d\n", ++cases);
printf("Surveillance is %spossible.\n", solution.n ? "" : "im");
puts("");
//printf("%d\n", solution.n);
}
return 0;
}
/*
20
0 0
0 -1
-1 -1
-1 1
2 1
2 -3
-3 -3
-3 3
4 3
4 -5
-5 -5
-5 3
-4 3
-4 -4
3 -4
3 2
-2 2
-2 -2
1 -2
1 0
*/
文章定位：
