Code: Select all
import java.awt.*;
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader dat1=new BufferedReader(new InputStreamReader(System.in));
//BufferedReader dat1 = new BufferedReader(new FileReader("c:/input.txt"));
//PrintWriter System.out = new PrintWriter(new FileWriter("c:/out.txt"));
int stevec=0;
while(true) {
String vrstica=dat1.readLine();
//System.out.println(vrstica);
StringTokenizer st=new StringTokenizer(vrstica);
if(st.countTokens()==0) continue;
int stPol=Integer.parseInt(st.nextToken());
//System.out.println("stPol: "+stPol);
int stRop=Integer.parseInt(st.nextToken());
//System.out.println("stRop: "+stRop);
int stPreb=Integer.parseInt(st.nextToken());
//System.out.println("stPreb: "+stPreb);
if(stPol==0 && stRop==0 && stPreb==0) break;
Tocka[] policaji=new Tocka[stPol];
Tocka[] roparji=new Tocka[stRop];
Tocka[] prebivalci=new Tocka[stPreb];
int yp=1000;
int ip=-1;
int yr=1000;
int ir=-1;
if(stevec>0) System.out.println();
System.out.println("Data set "+ ++stevec + ":");
for(int i=0; i<stPol; ++i) {
vrstica=dat1.readLine();
//System.out.println("vrstica: "+vrstica);
StringTokenizer st1=new StringTokenizer(vrstica);
String s1=st1.nextToken();
int stevilo1=Integer.parseInt(s1);
//System.out.println("stevilo1: "+stevilo1);
String s2=st1.nextToken();
int stevilo2=Integer.parseInt(s2);
//System.out.println("stevilo2: "+stevilo2);
policaji[i]=new Tocka(stevilo1, stevilo2);
if(stevilo2<yp) {
yp=stevilo2;
ip=i;
}
}
//System.out.println("yp: "+yp);
for(int i=0; i<stRop; ++i) {
vrstica=dat1.readLine();
StringTokenizer st1=new StringTokenizer(vrstica);
String s1=st1.nextToken();
int stevilo1=Integer.parseInt(s1);
//System.out.println("stevilo1: "+stevilo1);
String s2=st1.nextToken();
int stevilo2=Integer.parseInt(s2);
//System.out.println("stevilo2: "+stevilo2);
roparji[i]=new Tocka(stevilo1, stevilo2);
if(stevilo2<yr) {
yr=stevilo2;
ir=i;
}
//System.out.println("ir: "+ir);
}
//System.out.println("yr: "+yr);
for(int i=0; i<stPreb; ++i) {
vrstica=dat1.readLine();
StringTokenizer st1=new StringTokenizer(vrstica);
String s1=st1.nextToken();
int stevilo1=Integer.parseInt(s1);
//System.out.println("stevilo1: "+stevilo1);
String s2=st1.nextToken();
int stevilo2=Integer.parseInt(s2);
//System.out.println("stevilo2: "+stevilo2);
prebivalci[i]=new Tocka(stevilo1, stevilo2);
}
// naredi kompleksno ovojnico policajev
Polygon p=new Polygon();
if(stPol>2) {
p=ovojnica(policaji, ip);
}
//izpisi(p.xpoints);
//izpisi(p.ypoints);
//System.out.println(p.npoints);
// naredi kompleksno ovojnico roparjev
Polygon r=new Polygon();
if(stRop>2) {
r=ovojnica(roparji, ir);
}
//izpisi(r.xpoints);
//izpisi(r.ypoints);
//System.out.println(r.npoints);
//System.out.println((new Tocka(5,5)).naRobu(r));
// sprehodi se po prebivalcih
for(int i=0; i<stPreb; ++i) {
//System.out.println(""+prebivalci[i]+"");
if(stPol>2) {
if(p.contains(prebivalci[i].x, prebivalci[i].y) || prebivalci[i].naRobu(p)){
System.out.println(" Citizen at "+prebivalci[i]+" is safe.");
continue;
}
}
if(stRop>2) {
if(r.contains(prebivalci[i].x, prebivalci[i].y) || prebivalci[i].naRobu(r)){
System.out.println(" Citizen at "+prebivalci[i]+" is robbed.");
continue;
}
}
if(stPol<3 && stRop<3) System.out.println(" Citizen at "+prebivalci[i]+" is neither.");
else System.out.println(" Citizen at "+prebivalci[i]+" is neither.");
}
}
//dat1.close();
//System.out.close();
}
/* private static void izpisi(int[] t) {
int d=t.length;
for(int i=0; i<d; ++i) {
if(i>0) System.out.print(" ");
System.out.print(t[i]);
}
System.out.println();
}
private static void izpisi(double[] t) {
int d=t.length;
for(int i=0; i<d; ++i) {
if(i>0) System.out.print(" ");
System.out.print(t[i]);
}
System.out.println();
}*/
public static void izpisiTabelo(Tocka[] t) {
int d=t.length;
for(int i=0; i<d; ++i) {
if(i>0) System.out.print(" ");
System.out.print(t[i]);
}
System.out.println();
}
public static Polygon ovojnica(Tocka[] tocke, int k) {
Polygon p=new Polygon();
p.addPoint(tocke[k].x, tocke[k].y);
Tocka zacetna=tocke[k].kopiraj();
Tocka trenutna=zacetna.kopiraj();
double kot=0;
int d=tocke.length;
int preskoci=k;
//System.out.println("k: "+k);
for(int i=0; i<d-1; ++i) {
//System.out.print("trenutna: "); System.out.println(trenutna);
double[] nasl=poisciNaslednjo(trenutna,tocke,kot, preskoci);
Tocka naslednja=new Tocka((int)nasl[0],(int)nasl[1]);
//System.out.print("naslednja: "); System.out.println(naslednja);
kot=nasl[2];
//System.out.println(" kot: "+kot);
//System.out.print("naslednja: "); izpisi(naslednja);
p.addPoint(naslednja.x, naslednja.y);
trenutna=naslednja;
preskoci=(int)nasl[3];
//izpisi(p.xpoints);
//izpisi(p.ypoints);
}
return p;
}
public static double[] poisciNaslednjo(Tocka trenutna, Tocka[] tocke, double kotp, int preskoci) {
double[] n=new double[4];
double k=361;
//System.out.println("trenutna: "+trenutna);
int x1=trenutna.x;
int y1=trenutna.y;
int pr=preskoci;
//System.out.println("preskoci: "+pr);
int d=tocke.length;
//System.out.println("d: "+d);
for(int i=0; i<d; ++i) {
if(i==preskoci) continue;
//System.out.println("i: "+i);
//System.out.println("x1: "+x1);
//System.out.println("y1: "+y1);
int x2=tocke[i].x;
//System.out.println("x2: "+x2);
int y2=tocke[i].y;
//System.out.println("y2: "+y2);
if(x1==x2 && y1==y2) {
n[0]=x2;
n[1]=y2;
n[2]=-1;
pr=i;
continue;
}
//System.out.println("kotp: "+kotp);
double kot=kot(x1, y1, x2, y2)-kotp;
if(kot>=0 && kot<k) {
//System.out.println("kot: "+kot);
k=kot;
n[0]=x2;
n[1]=y2;
n[2]=kot;
pr=i;
}
}
n[3]=pr;
//System.out.print("n: ");
//izpisi(n);
return n;
}
public static double kot(int x1, int y1, int x2, int y2) {
if ((x2 == x1) && (y2 == y1)) return -1.0;
if (x2 == x1) return ((y2 > y1) ? 90 : 270);
double theta = Math.atan((double)((y2-y1)/(x2-x1)));
theta *= 360/(2*Math.PI);
if (x2 > x1) return ((y2 >= y1) ? theta : 360 + theta);
else return (180+theta);
}
}
class Tocka {
int x;
int y;
public Tocka(int x, int y) {
this.x=x;
this.y=y;
}
public String toString() {
return "("+this.x+","+this.y+")";
}
public Tocka kopiraj() {
return new Tocka(this.x, this.y);
}
public boolean enaka(Tocka t) {
if(this.x==t.x && this.y==t.y) return true;
return false;
}
public boolean naRobu(Polygon p) {
int n=p.npoints;
//System.out.println("n: "+n);
for(int i=0; i<n-1; ++i) {
//System.out.println("i: "+i);
Tocka trenutna=new Tocka(p.xpoints[i], p.ypoints[i]);
//System.out.println(" trenutna: "+trenutna);
Tocka naslednja=new Tocka(p.xpoints[i+1], p.ypoints[i+1]);
//System.out.println(" naslednja: "+naslednja);
//System.out.println(" this: "+this);
int x1=trenutna.x;
//System.out.println("x1: "+x1);
int y1=trenutna.y;
//System.out.println("y1: "+y1);
int x2=naslednja.x;
//System.out.println("x2: "+x2);
int y2=naslednja.y;
//System.out.println("y2: "+y2);
if(x1==x2 && y1==y2 && x!=x1) continue;
//poskrbimo, da je y1<=y2
if(y2<y1) {
int t=x2; x2=x1; x1=t;
t=y2; y2=y1; y1=t;
}
if(x1<x2) {
if(x<x1 || x>x2 || y<y1 || y>y2) continue;
}
else if(x2<x1) {
if(x<x2 || x>x1 || y<y1 || y>y2) continue;
}
if(x1*(y2-y) +x2*(y-y1) + x*(y1-y2)==0) {
return true;
}
}
return false;
}
}