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
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define SIZE 1000
#define MAX 10000000
#define NOT_PARALLEL true
#define eps 1e-9
struct point{
	int x, y;
};
int cmp(const void* a, const void* b){
	
	struct point aa = *(struct point*)a;
	struct point bb = *(struct point*)b;
	
	if(aa.x < bb.x)		return -1;
	else if(aa.x == bb.x){
		if(aa.y < bb.y)	return -1;
		else			return 1;
	}
	else				return 1;
}

bool m(int x1, int y1, int x2, int y2, int x3, int y3){	
	
	double m1 = MAX, m2 = MAX;
	
	if((x3-x1) != 0)	m1 = (double)(y3-y1)/(x3-x1);
	if((x3-x2) != 0)	m2 = (double)(y3-y2)/(x3-x2);
	
	if(m1 == m2 || m1 == -m2)	return ~NOT_PARALLEL;
	else						return NOT_PARALLEL;
}

int cross(struct point o, struct point a, struct point b){
	
	bool result = m(a.x, a.y, b.x, b.y, o.x, o.y);
	
	if(result)	return ((a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x));
	else		return ((pow((a.x-o.x), 2)+pow((a.y-o.y), 2))>(pow((b.x-o.x), 2)+pow((b.y-o.y), 2)))?-1:1;
}

void convex_hall(int num, struct point* tmp, struct point* convex, int *count){
	
	int i, j, t, c;
	
	qsort(tmp, num, sizeof(struct point), cmp);
	
	for(i=0, c=0;i<num;++i){
		while(c >= 2 && cross(convex[c-2], convex[c-1], tmp[i]) <= 0)	--c;
		convex[c++] = tmp[i];
	}
	for(i=num-2, t=c+1;i>=0;--i){
		while(c >= t && cross(convex[c-2], convex[c-1], tmp[i]) <= 0)	--c;
		convex[c++] = tmp[i];
	}
	(*count) = c - 1;
}

void calc_area(int* count, struct point* convex, double *area){
	(*area) = 0.0;
	for(int i=1;i<(*count);++i)	(*area) = (*area)+(convex[i-1].x*convex[i].y)-(convex[i].x*convex[i-1].y);
	(*area) = (*area)+(convex[(*count)-1].x*convex[0].y)-(convex[0].x*convex[(*count)-1].y);
}

void calc(int num, struct point* tmp, struct point* convex, int *count, double *area){
	convex_hall(num, tmp, convex, count);
	calc_area(count, convex, area);
}

bool determine1(int count, struct point tmp[SIZE], struct point p, double area){
	
	int i, count_tmp;
	double area_tmp;
	struct point old_convex[SIZE], new_convex[SIZE];
	
	for(i=0;i<count;++i)	old_convex[i] = tmp[i];
	old_convex[count++]	= p;
	calc(count, old_convex, new_convex, &count_tmp, &area_tmp);
	
	if((area_tmp-area) < eps && area > eps)return true;
	else								   return false;
}

bool determine2(int count, struct point* tmp, struct point p){
	
	qsort(tmp, count, sizeof(struct point), cmp);
	
	if((p.x >= tmp[0].x && p.y >= tmp[0].y) && (p.x <= tmp[count-1].x && p.y <= tmp[count-1].y))
			return true;
	else	return false;
}

int main(){
	
	int cases=1, i, j, cops, count_c, robs, count_r, people;
	double area_c, area_r;
	struct point c[SIZE], r[SIZE], p, convex_c[SIZE], convex_r[SIZE];
	
	while(scanf("%d%d%d", &cops, &robs, &people) == 3){
		if(cops == 0 && robs == 0 && people == 0)	break;
		
		for(i=0;i<cops;++i)	scanf("%d%d", &c[i].x, &c[i].y);
		calc(cops, c, convex_c, &count_c, &area_c);
		for(i=0;i<robs;++i)	scanf("%d%d", &r[i].x, &r[i].y);
		calc(robs, r, convex_r, &count_r, &area_r);
		
		printf("Data set %d:\n", cases++);
		for(i=0;i<people;++i){
			scanf("%d%d", &p.x, &p.y);
			bool in_c = false, in_r = false;
			if(area_c > eps)	in_c = determine1(count_c, convex_c, p, area_c);
			else if(count_c > 1 && (convex_c[0].x != convex_c[count_c-1].x || convex_c[0].y != convex_c[count_c-1].y))	
								in_c = determine2(count_c, convex_c, p);
			if(in_c)		printf("     Citizen at (%d,%d) is safe.\n", p.x, p.y);
			else{
				if(area_r > eps)in_r = determine1(count_r, convex_r, p, area_r);
				else if(count_r > 1 && (convex_r[0].x != convex_r[count_r-1].x || convex_r[0].y != convex_r[count_r-1].y))	
								in_r = determine2(count_r, convex_r, p);
				if(in_r)	printf("     Citizen at (%d,%d) is robbed.\n", p.x, p.y);
				else		printf("     Citizen at (%d,%d) is neither.\n", p.x, p.y);
			}
		}
		printf("\n");
	}
	return 0;
}