You are to simulate a game of Cops and Robbers. In this game, cops, robbers, and other citizens are represented as points in a two-dimensional plane. A citizen is said to be safe if it is within a triangle formed by three cops. A citizen is said to be robbed if it is not safe and is within a triangle formed by three robbers. A citizen is neither safe nor robbed if it satisfies neither of the above conditions. For purposes of this problem, a triangle consists of three points, and a point is within a triangle if it is inside or on the boundary of the triangle.
In the following diagram, filled circles represent cops, filled squares represent robbers, and filled triangles represent citizens. Dashed lines indicate triangles formed by cops or robbers
In this example, citizens A and B are safe, citizen C is robbed, and citizen D is neither.
Given a set of cops and robbers and several citizen queries, efficiently determine whether each citizen is safe, robbed, or neither.
The input consists of several data sets. The first line of each data set contains three non-negative integers c, r, and o: the number of cops, robbers, and other citizens, respectively. c, r, and o will each be at most 200. The next c lines contain the (x, y) coordinates of each cop, one per line. The next r lines contain the (x, y) coordinates of each robber, one per line. The next o lines contain the (x, y) coordinates of each other citizen, one per line. All coordinates are integers between -500 and 500 inclusive.
Your program must stop processing input when it encounters a data set in which c, r, and o are all zero.
Output for each data set begins with a line identifying the data set. For each other citizen in the data set, output the line
Citizen at (x,y) is status.
where (x,y) is the location of the citizen from the input and status is one of safe, robbed or neither. Follow the format given in the Sample Output. Leave a blank line after the output from each data set.
3 3 2 0 0 10 0 0 10 20 20 20 0 0 20 5 5 15 15 3 3 1 0 0 10 0 0 10 20 20 20 0 0 20 40 40 0 0 0
Data set 1: Citizen at (5,5) is safe. Citizen at (15,15) is robbed. Data set 2: Citizen at (40,40) is neither.
民只要能在三警察成的三角形就是 safe.
否如果在三歹徒成的三角形就是 robbed.
都不是就是 neither.
由於很多，不可以三去判民是不是在三角形部。
不仿警察的座做一凸包，然後判是否在三角形部(使用射法判)。
//因凸包可以切成很多三角形, 同理歹徒。
得凸包上也可以算的。
special cases:
警察/歹徒只有, 特判定不可能 safe/robbed.
凸包做出只有(即段), 上也是可以算的。
#include <stdio.h>
#include <algoithm>
#include <math.h>
using namespace std;
struct Pt {
double x, y;
bool operator<(const Pt &a) const {
if(x != a.x)
return x < a.x;
return y < a.y;
}
};
#define eps 1e-8
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 onSeg(Pt a, Pt b, Pt p) {
if(min(a.x, b.x)-eps <= p.x && p.x <= max(a.x, b.x)+eps &&
min(a.y, b.y)-eps <= p.y && p.y <= max(a.y, b.x)+eps &&
fabs(cross(a, b, p)) < eps)
return 1;
return 0;
}
int inPolygon(Pt p[], int n, Pt q) {
int i, j, k = 0;
for(i = 0, j = n-1; i < n; j = i++) {
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)
k++;
if(onSeg(p[i], p[j], q))
return 1;
}
return k&1;
}
int monotone(Pt p[], int n, Pt ch[]) {
sort(p, p+n);
int i, m = 0, t;
for(i = 0; i < n; i++) {
while(m >= 2 && cross(ch[m-2], ch[m-1], p[i]) <= 0)
m--;
ch[m++] = p[i];
}
for(i = n-1, t = m+1; i >= 0; i--) {
while(m >= t && cross(ch[m-2], ch[m-1], p[i]) <= 0)
m--;
ch[m++] = p[i];
}
return m-1;
}
int main() {
int cases = 0;
int C, R, O;
Pt cop[205], robber[205], q;
Pt hcop[205], hrobber[205];
int i, j, k;
while(scanf("%d %d %d", &C, &R, &O) == 3) {
if(C == 0 && R == 0 && O == 0)
break;
for(i = 0; i < C; i++)
scanf("%lf %lf", &cop[i].x, &cop[i].y);
for(i = 0; i < R; i++)
scanf("%lf %lf", &robber[i].x, &robber[i].y);
int nC, nR;
nC = monotone(cop, C, hcop);
nR = monotone(robber, R, hrobber);
printf("Data set %d:\n", ++cases);
while(O--) {
scanf("%lf %lf", &q.x, &q.y);
printf(" Citizen at (%.0lf,%.0lf) is ", q.x, q.y);
int f1 = inPolygon(hcop, nC, q);
if(f1 && C >= 3)
puts("safe.");
else {
int f2 = inPolygon(hrobber, nR, q);
if(f2 && R >= 3)
puts("robbed.");
else
puts("neither.");
}
}
puts("");
}
return 0;
}
文章定位：
