361 - Cops and Robbers

All about problems in Volume 3. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
bjelakrez
New poster
Posts: 1
Joined: Tue May 06, 2008 3:35 pm

361 - WA

Post by bjelakrez »

I have no idea why i keep getting WA. my java program works correctly on every case mentioned in this forum. Could anyone please be so kind as to check for an error, i don't find any

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;
	}
}
thank you very much.
Top
Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:
Contact Jan

Re: 361 - WA

Post by Jan »

Search the board first. Don't open a new thread if there is one already.

http://acm.uva.es/board/viewtopic.php?f=4&t=696
Ami ekhono shopno dekhi...
HomePage
Top
zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Location: CSE-DU, Bangladesh
Contact:
Contact zobayer

Re: 361 - Cops and Robbers

Post by zobayer »

Problem Link: http://uva.onlinejudge.org/external/3/361.html
Don't know whats going wrong, getting WA in this problem. I have tested inputs already posted on these forums, but those could not help me to find the bug. Here is my code:

Code: Select all

#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;

const int MAXN = 256;

struct point { int x, y; };
struct region { bool ok; int np; point P[MAXN]; };

region K[2];
point P[MAXN], C[MAXN], P0;

inline int triArea2(const point &a, const point &b, const point &c) {
	return (a.x*(b.y-c.y) + b.x*(c.y-a.y) + c.x*(a.y-b.y));
}

inline int sqDist(const point &a, const point &b) {
	return ((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}

inline bool comp(const point &a, const point &b) {
	int d = triArea2(P0, a, b);
	if(d < 0) return false;
	if(!d && sqDist(P0, a) > sqDist(P0, b)) return false;
	return true;
}

inline bool normal(const point &a, const point &b) {
	return ((a.x==b.x) ? a.y < b.y : a.x < b.x);
}

inline bool issame(const point &a, const point &b) {
	return (a.x == b.x && a.y == b.y);
}

inline void makeUnique(int &np) {
	sort(&P[0], &P[np], normal);
	np = unique(&P[0], &P[np], issame) - P;
}

void convexHull(int &np, int &nc) {
	int i, j, pos = 0;
	for(i = 1; i < np; i++)
		if(P[i].y<P[pos].y || (P[i].y==P[pos].y && P[i].x<P[pos].x))
			pos = i;
	swap(P[0], P[pos]);
	P0 = P[0];
	sort(&P[1], &P[np], comp);
	for(i = 0; i < 3; i++) C[i] = P[i];
	for(i = j = 3; i < np; i++) {
		while(triArea2(C[j-2], C[j-1], P[i]) < 0) j--;
		C[j++] = P[i];
	}
	nc = j;
}

bool inside(point *p, int n, point &m) {
	if(n == 1) return p[0].x == m.x && p[0].y == m.y;
	if(n == 2) return (sqDist(p[0], m) + sqDist(m, p[1]) <= sqDist(p[0], p[1]));
	int lt = n - 1, rt = 1, mid, dir, temp;
	while(lt - rt > 1) {
		mid = (lt + rt) >> 1;
		dir = triArea2(p[0], p[mid], m);
		if(dir < 0) lt = mid;
		else if(dir > 0) rt = mid;
		else return (sqDist(p[0], m) + sqDist(m, p[mid]) <= sqDist(p[0], p[mid]));
	}
	temp = abs(triArea2(p[0], p[rt], m)) + abs(triArea2(p[rt], p[lt], m)) + abs(triArea2(p[lt], p[0], m));
	return (temp == abs(triArea2(p[0], p[rt], p[lt])));
}

int main() {
	int n[2], c[2], i, kd, cit, cs = 1;
	point m;
	while(scanf("%d%d%d", &n[0], &n[1], &cit)==3 && (n[0] + n[1] + cit)) {
		for(kd = 0; kd < 2; kd++) {
			for(i = 0; i < n[kd]; i++) scanf("%d%d", &P[i].x, &P[i].y);
			if(n[kd] < 3) { K[kd].ok = 0; continue; }
			K[kd].ok = 1;
			makeUnique(n[kd]);
			if(n[kd] < 3) {
				K[kd].np = n[kd];
				for(i = 0; i < n[kd]; i++) K[kd].P[i] = P[i];
				continue;
			}
			convexHull(n[kd], c[kd]);
			K[kd].np = c[kd];
			for(i = 0; i < c[kd]; i++) K[kd].P[i] = C[i];
		}
		printf("Data set %d:\n", cs++);
		for(i = 0; i < cit; i++) {
			scanf("%d%d", &m.x, &m.y);
			if(K[0].ok && inside(K[0].P, K[0].np, m)) printf("     Citizen at (%d,%d) is safe.\n", m.x, m.y);
			else if(K[1].ok && inside(K[1].P, K[1].np, m)) printf("     Citizen at (%d,%d) is robbed.\n", m.x, m.y);
			else printf("     Citizen at (%d,%d) is neither.\n", m.x, m.y);
		}
		printf("\n");
	}
	return 0;
}
If I have < 3 cops or robbers, I will ignore them. Then I find their convex hulls, which might not be strictly convex. Then I determine where the citizen falls... I think this is correct.

Please help me, thanks in advance :)
You should not always say what you know, but you should always know what you say.
Top
ujjal.ruet
New poster
Posts: 15
Joined: Thu Sep 02, 2010 3:10 pm
Location: Dhaka,Bangladesh
Contact:
Contact ujjal.ruet

Re: 361 Again!!!

Post by ujjal.ruet »

Can I have the .exe of your AC code for 361.I am getting WA in this problem also.
Or,please tell me what is the critical test case for which I should concerned.

Or,please have a look on my code.

Code: Select all

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<queue>
#include<vector>
#include<map>
using namespace std;
#define EPS 1e-9

struct PT{

    int x,y;

}c[210],r[210],p[210];





 double dist(PT &a,PT &b){
     return (sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)));
     }




double area(int x1,int y1,int x2,int y2,int x3,int y3){
   double a;

    a=0.5*((x1*y2+x2*y3+x3*y1)-(y1*x2+y2*x3+y3*x1));

     return fabs(a);
}




int ifinside(PT k,PT ul,PT lr,PT tr){

/*
double a[5];

a[0]=dist(ul,lr);
a[1]=dist(lr,tr);
a[2]=dist(ul,tr);

sort(a,a+3);

if((a[0]+a[1])>a[2]){
*/
      double a1,a2,a3,a4;

         a1=area(k.x,k.y,ul.x,ul.y,lr.x,lr.y);
         a2=area(k.x,k.y,ul.x,ul.y,tr.x,tr.y);
         a3=area(k.x,k.y,tr.x,tr.y,lr.x,lr.y);
         a4=area(ul.x,ul.y,lr.x,lr.y,tr.x,tr.y);



     if((a1+a2+a3-a4)<=EPS)
         return 1;
      else
      return 0;

/*}
else
      return 0;
*/
}



int main(){
int cr,rb,ct,i,j,k,l,cops,robbed,set;


//freopen("361.txt","r",stdin);

set=0;
while(scanf("%d %d %d",&cr,&rb,&ct)==3){

if(cr==0 && rb==0 &&ct==0)
 break;




for(i=0;i<cr;i++){
scanf("%d %d",&c[i].x,&c[i].y);
}

for(i=0;i<rb;i++){
scanf("%d %d",&r[i].x,&r[i].y);
}


printf("Data set %d:\n",++set);

for(i=0;i<ct;i++){
scanf("%d %d",&p[i].x,&p[i].y);



cops=0;
for(j=0;j<cr-2;j++){
  for(k=j+1;k<cr-1;k++){
       { if(ifinside(p[i],c[j],c[k],c[k+1])==1)
                {cops=1;break;}
      }
    if(cops==1)  break;      }

if(cops==1)  break;
}



robbed=0;
for(j=0;j<rb-2;j++){
  for(k=j+1;k<rb-1;k++){
     {    if(ifinside(p[i],r[j],r[k],r[k+1])==1)
                {robbed=1;break;}
      }
    if(robbed==1)  break;      }

if(robbed==1)  break;
}





if(cops==1)
printf("     Citizen at (%d,%d) is safe.\n",p[i].x,p[i].y);
else if(robbed==1)
printf("     Citizen at (%d,%d) is robbed.\n",p[i].x,p[i].y);
else
printf("     Citizen at (%d,%d) is neither.\n",p[i].x,p[i].y);

}

printf("\n");
}
return 0;
}

my mail id is

Code: Select all

usuttra@yahoo.com
please make me concerned.
Top
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Re: 361 Again!!!

Post by sohel »

You can find EXEs of most of the UVa problems in this site - http://uvatoolkit.com/problemssolve.php
Top
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 361 - Cops and Robbers

Post by uDebug »

Thanks to Mikhail Goncharov there's testing / debugging input at:

http://www.udebug.com/UVa/361
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.
Top
Post Reply

Return to “Volume 3 (300-399)”