1. 

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS10
* Problem: 361 - Cops and Robbers
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=5&page=show_problem&problem=297
*
* @author Evgeni Pavlidis
* @version 1.0, 06/02/2010
*
* Method : Comp. Geometry - Convex Hull - Graham Scan
* Status : Accepted
* Runtime: 0.476
*/

import java.io.*;
import java.util.*;

class Main {

public static final double EPSILON = 0.000000000001;
public static final int COPS = 0;
public static final int ROBBERS = 1;
public static final int CITIZENS = 2;

static class Point implements Comparable<Point>
{
final int x,y;
double dist;
double angle;

Point(int x, int y)
{ this.x = x; this.y = y; }

public String toString()
{ return "("+x+","+y+")"; }

public int hashCode()
{ return (x << 16) + y; }

public boolean equals(Object other)
{ return this.hashCode() == ((Point)other).hashCode(); }

public int compareTo(Point b)
{
if(this.angle < b.angle-EPSILON)
return -1;
if(this.angle > b.angle+EPSILON)
return 1;

if(this.dist < b.dist-EPSILON)
return -1;
if(this.dist > b.dist+EPSILON)
return 1;

return 0;
}
}


private static double getAngle(Point a, Point b)
{ return Math.atan((double)(a.y-b.y)/(double)(a.x-b.x)); }

private static long crossProduct(Point m, Point a, Point b)
{ return ((a.x - m.x)*(b.y - m.y) - (a.y - m.y)*(b.x - m.x)); }

private static long dotProduct(Point a, Point b)
{ return a.x*b.x + a.y*b.y; }

private static double dist(Point a, Point b)
{ return Math.sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y)); }

private static boolean isBetween(Point x, Point a, Point b)
{ return Math.abs(dist(x,a) + dist(x,b) - dist(a,b)) < EPSILON; }



static Point getMin(List<Point> list)
{
Point min = list.get(0);
for(Point l: list)
if(l.x < min.x || (l.x == min.x && l.y < min.y))
min = l;
return min;
}

static List<Point> buildHull(List<Point> list)
{
if(list.size() < 3)
return list;

// check if we have an one dimensional hull (a line)
if(list.size() == 3)
{
if(isBetween(list.get(1), list.get(0), list.get(2)))
list.remove(1);
return list;
}

Stack<Point> stack = new Stack<Point>();
stack.push(list.get(0));
stack.push(list.get(1));
stack.push(list.get(2));

Point head, tail, middle;

int i = 3;
while(i < list.size())
{
tail = stack.pop();
middle = stack.pop();
head = list.get(i);

if(crossProduct(middle, tail, head) > 0)
{
stack.push(middle);
stack.push(tail);
stack.push(head);
i++;
}
else
stack.push(middle);
}

return new ArrayList<Point>(stack);
}

static boolean isInHull(Point p, List<Point> hull)
{
if(hull == null || hull.size() == 0)
return false;

if(hull.size() == 1)
return (p.x == hull.get(0).x && p.y == hull.get(0).y);

if(hull.size() == 2)
return isBetween(p, hull.get(0), hull.get(1));

Point pivot = hull.get(0);
for(int i = 2; i < hull.size(); i++)
if(crossProduct(pivot, hull.get(i-1), p) >= 0 &&
crossProduct(hull.get(i-1), hull.get(i), p) >= 0 &&
crossProduct(hull.get(i), pivot, p) >= 0)
return true;

return false;
}




public static void main(String...args)
{
Scanner sc = new Scanner(System.in);
int dataSet = 1;

// saves the number of the points for cops,robbers and citizens
int[] numberOf = new int[3];

// saves the list of Points for cops and robbers
List<List<Point>> container = new ArrayList<List<Point>>();

// filter for removing duplicate points
Set<Point> filter = new HashSet<Point>();


while(true)
{
container.clear();

numberOf[COPS] = sc.nextInt();
numberOf[ROBBERS] = sc.nextInt();
numberOf[CITIZENS] = sc.nextInt();

if(numberOf[COPS] == 0 && numberOf[ROBBERS] == 0 && numberOf[CITIZENS] == 0)
break;

// process cops and robbers
for(int i = 0; i < 2; i++)
{
// read input coordinates
filter.clear();
for(int p = 0; p < numberOf[i]; p++)
filter.add(new Point(sc.nextInt(), sc.nextInt()));
container.add(new ArrayList<Point>(filter));


// build hull
if(numberOf[CITIZENS] > 0 && numberOf[i] > 2)
{
List<Point> points = container.get(i);

Point pivot = getMin(points);
for(Point p: points)
{
p.angle = getAngle(p, pivot);
p.dist = dist(p, pivot);
}
pivot.angle = -2000;

Collections.sort(points);
container.set(i, buildHull(points));
}
else
container.set(i, null);
}

// process citizens
System.out.println("Data set " + dataSet++ + ":");
for(int citizen = 0; citizen < numberOf[CITIZENS]; citizen++)
{
Point c = new Point(sc.nextInt(), sc.nextInt());

System.out.print(" Citizen at " + c + " is ");
if(isInHull(c, container.get(COPS)))
System.out.println("safe.");
else
if(isInHull(c, container.get(ROBBERS)))
System.out.println("robbed.");
else
System.out.println("neither.");
}
System.out.println();
}
}
}