Cops and Robbers

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.

Input

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

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.

Sample Input

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

Sample Output

Data set 1:
     Citizen at (5,5) is safe.
     Citizen at (15,15) is robbed.

Data set 2:
     Citizen at (40,40) is neither.

記得凸包邊上也可以算的。

special cases:
警察/歹徒只有兩個, 特別判定不可能為 safe/robbed.
凸包做出來只有兩個點(即線段), 線上也是可以算的。


#include <stdio.h>
#include <algorithm>
#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;
}