361 - Cops and Robbers

Ivan Golubev · Post by **Ivan Golubev** » Wed Sep 18, 2002 1:55 pm

Yes, citizen at (6,2) is safe.

One more time, summary to get accepted:
1. Use only integers to avoid precision errors.
2. If there less than 3 cops then citizen cannot be safe (of course, this also applied to robbers).
3. If citizen inside triangle or it at any line that forms the triangle or it at any vertex of the triangle -- it safe.

Anything else looks trivial and easy.

jpfarias · Post by **jpfarias** » Sat Oct 12, 2002 9:01 pm

if there are n >= 3 cops and all n cops are colinear, can a citizen be safe?

JP
jpfarias@lcc.ufrn.br

Ivan Golubev · Post by **Ivan Golubev** » Sat Oct 12, 2002 9:37 pm

jpfarias wrote:if there are n >= 3 cops and all n cops are colinear, can a citizen be safe?

Yes, it can be safe.

jpfarias · Post by **jpfarias** » Sun Oct 13, 2002 7:45 pm

Hi!

Here I am again...

I yet cannont solve this problem. I think the problem is with my algorithm wich finds if a point is inside a polygon. I'm using the winding count, but I think I've implemented it wrong.

Can anyone point me with an implementation of any good algorithm to find if a point is inside a polygon (and if it is in the border also). A C++ code would be better for me, but I also understand pascal, c and java (and others languages not acceptable by the judge).

Thanks in advance.

jpfarias · Post by **jpfarias** » Mon May 26, 2003 5:14 pm

Well, after a while I was decided to try again this problem!

I am now a more experienced programmer and know more algorithms to help me, so, on this problem I thought that Jarvin's March and Point in Poly are the one's of choice, togheter with point in seg.

So, my approach was:

Code: Select all


1. read in cops and robbers positions.
2. find the convex hull for the cops and/or robs if more then 2 cops/robbers
3. now, for each citizen:
    4. if more then 2 cops:
        5. if the citizen is in the same place of a cop or
               the citizen is between two cops (on a line) or
               the citizen is inside the convex hull
            6. the citizen is said to be safe
    7. else do the tests of 4 and 5 for the robs
    9. if not safe and not robbed
        10. the citizen is said to be neither

And this gives me WA

Can anyone help, or should I surrender?

JP!

galois_godel · Post by **galois_godel** » Wed May 28, 2003 3:10 pm

I don't know why my code for 361 is wrong?
my code is:
[cpp]
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
using namespace std;
#define infinity 1e20
#define EP 1e-10
#define N 10000
//#define double int

struct TPoint{
double x,y;
};
TPoint bp;
struct TLineSeg{
TPoint a,b;
};
int same1(TLineSeg l,TPoint r,TPoint s)
{
double temp;
double dx,dy,dx1,dy1,dx2,dy2;
dx=l.b.x-l.a.x;
dy=l.b.y-l.a.y;
dx1=r.x-l.a.x;
dy1=r.y-l.a.y;
dx2=s.x-l.a.x;
dy2=s.y-l.a.y;
temp=(dx*dy1-dy*dx1)*(dx*dy2-dy*dx2);
return (temp>=0);
}

double max(double a,double b)
{
if(a>b)
return a;
else
return b;
}
double min(double a,double b)
{
if(a<b)
return a;
else
return b;
}
float distance(TPoint p1,TPoint p2)
{
return(sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)));
}

float multiply(TPoint p1,TPoint p2,TPoint p0)
{
return((p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y));
}

int intersect(TLineSeg u,TLineSeg v)
{
return( (max(u.a.x,u.b.x)>=min(v.a.x,v.b.x))&&
(max(v.a.x,v.b.x)>=min(u.a.x,u.b.x))&&
(max(u.a.y,u.b.y)>=min(v.a.y,v.b.y))&&
(max(v.a.y,v.b.y)>=min(u.a.y,u.b.y))&&
(multiply(v.a,u.b,u.a)*multiply(u.b,v.b,u.a)>=0)&&
(multiply(u.a,v.b,v.a)*multiply(v.b,u.b,v.a)>=0));
}

int online(TLineSeg l,TPoint p)
{
return( (multiply(l.b,p,l.a)==0)&&( ((p.x-l.a.x)*(p.x-l.b.x)<0 )||( (p.y-l.a.y)*(p.y-l.b.y)<0 )) );
}

int Euqal_Point(TPoint p1,TPoint p2)
{
return((fabs(p1.x-p2.x)<EP)&&(fabs(p1.y-p2.y)<EP));
}

int intersect_A(TLineSeg u,TLineSeg v)
{
return((intersect(u,v))&&
(!Euqal_Point(u.a,v.a))&&
(!Euqal_Point(u.a,v.b))&&
(!Euqal_Point(u.b,v.a))&&
(!Euqal_Point(u.b,v.b))&&
(!online(u,v.a))&&
(!online(u,v.b))&&
(!online(v,u.a))&&
(!online(v,u.b)));
}

int InsidePolygon(int vcount,TPoint Polygon[],TPoint q)
{
int c=0,i,n;
TLineSeg l1,l2;

l1.a=q;
l1.b=q;
l1.b.x=infinity;
n=vcount;
for (i=0;i<vcount;i++)
{
l2.a=Polygon;
l2.b=Polygon[(i+1)%n];
// cout<<i<<" "<<online(l1,Polygon[(i+1)%n])<<" "<<intersect_A(l1,l2)<<endl;
if( Euqal_Point(q,l2.a) ||Euqal_Point(q,l2.b))
return 1;
if(online(l2,q))
return 1;
if((intersect_A(l1,l2))||
(
(online(l1,Polygon[(i+1)%n]))&&
(
(!online(l1,Polygon[(i+2)%n]))&&
(!same1(l1,Polygon,Polygon[(i+2)%n]))
||
(online(l1,Polygon[(i+2)%n]))&&
(!same1(l1,Polygon,Polygon[(i+3)%n]))
)
)
) c++;

// cout<<c<<endl;
}
//cout<<c<<endl;
return(c%2!=0);
}
void swap(TPoint *a,TPoint *b)
{
TPoint temp=*a;
*a=*b;
*b=temp;
}
/*
int cmp(const void *a,const void *b)
{
TPoint *pa=(TPoint *)a;
TPoint *pb=(TPoint *)b;
double ra=sqrt((pa->x-bx)*(pa->x-bx)+(pa->y-by)*(pa->y-by));
double rb=sqrt((pb->x-bx)*(pb->x-bx)+(pb->y-by)*(pb->y-by));
if(ra<EP)
return 1;
if(rb<EP)
return -1;
double ka=acos((pa->x-bx)/ra);
double kb=acos((pb->x-bx)/rb);
if(fabs(ka-kb)<1e-6)
if(ra>rb)
return 1;
else if(ra<rb)
return -1;
else
return 0;
else if(ka>kb)
return 1;
else
return -1;
//return anglea-angleb;
}*/
int cmp(const void *a,const void *b)
{
double ka,kb;
double da,db;
double ax=((TPoint *)a)->x-bp.x;
double ay=((TPoint *)a)->y-bp.y;
// cout<<" int cmp: "<<bx<<" "<<by<<endl;
double bx=((TPoint *)b)->x-bp.x;
double by=((TPoint *)b)->y-bp.y;

da=sqrt(ax*ax+ay*ay);
db=sqrt(bx*bx+by*by);
ka=acos(ax/da);
kb=acos(bx/db);
if(fabs(ka-kb)<EP)
if(da>db)
return 1;
else if(da<db)
return -1;
else
return 0;
else if(ka>kb)
return 1;
else
return -1;

}
void output(TPoint p[],int len)
{
cout<<"DEBUG IN OUTPUT"<<endl;
int i;
for(i=0;i<len;i++)
{
cout<<p.x<<" "<<p.y<<endl;
}
cout<<"END OF DEBUG IN OUPUT"<<endl;
}
int convexhull(TPoint p[],int len)
{
int mini=0;
TPoint pp[N];
int pplen;
int i,j;
for(i=1;i<len;i++)
{
if((p[mini].y)>(p.y) || ( fabs(p[mini].y-p.y)<EP && p[mini].x>p.x ))
mini=i;
}
if(mini)
swap(&p[mini],&p[0]);
bp=p[0];
if(len>1)
qsort((void *)(p+1),len-1,sizeof(p[0]),cmp);
//output(p,len);

pp[0]=p[0];
pp[1]=p[1];
pp[2]=p[2];
pplen=3;
j=3;
while(fabs(multiply(pp[0],pp[1],pp[2]))<EP )
{
pp[1]=pp[2];
if(j<len)
pp[2]=p[j++];
else
{
pplen--;
break;
}

}

for(;j<len;j++)
{
// pp[pplen++]=p[j];
// cout<<" for "<<j<<" "<<p[j].x<<" "<<p[j].y<<endl;
while(multiply(p[j],pp[pplen-1],pp[pplen-2])>0 && pplen>2 )
{
// cout<<" multiply(p[j],p[pplen-1],p[pplen-2])="<<multiply(p[j],p[pplen-1],p[pplen-2])<<endl;
pplen--;
// cout<<j<<endl;
}
// cout<<"outwhile multiply(p[j],p[pplen-1],p[pplen-2])="<<multiply(p[j],p[pplen-1],p[pplen-2])<<endl;
pp[pplen++]=p[j];

}
for(i=0;i<pplen;i++)
p=pp;
return pplen;
}

TPoint cop[N];
TPoint rob[N];
int c,r,o;
void input()
{
int i;
for(i=0;i<c;i++)
cin>>cop[i].x>>cop[i].y;
if(c>2)
c=convexhull(cop,c);
//cout<<c<<endl;
/// output(cop,c);
for(i=0;i<r;i++)
cin>>rob[i].x>>rob[i].y;
if(r>2)
r=convexhull(rob,r);
}
void slv()
{
int i;
TPoint citizen;
for(i=0;i<o;i++)
{
cin>>citizen.x>>citizen.y;
if(InsidePolygon(c,cop,citizen) )
cout<<" Citizen at ("<<citizen.x<<","<<citizen.y<<") is "<<"safe."<<endl;
else if(InsidePolygon(r,rob,citizen) )
cout<<" Citizen at ("<<citizen.x<<","<<citizen.y<<") is "<<"robbed."<<endl;
else
cout<<" Citizen at ("<<citizen.x<<","<<citizen.y<<") is "<<"neither."<<endl;
}
cout<<endl;
}

int main()
{

int cas=0;
while(cin>>c>>r>>o)
{
if(c==0 && r==0 && o==0)
break;
cout<<"Data set "<<++cas<<":"<<endl;
input();
slv();
}

return 0;
}
[/cpp]

jpfarias · Post by **jpfarias** » Sun Jun 15, 2003 9:07 pm

It can be right, but you will never know until you get AC!

I'm really angry with the judge because of a problem, read my post on problem 329 and you will see why!

JP!

Observer · Post by **Observer** » Tue Jan 06, 2004 1:14 pm

I got accepted after ~50 trials, sice I've forgotten that if number of cops < 3, then no one can be safe. Similar thing applies to robbers.

(How I wish I had read Ivan Golubev's previous posts carefully

)

minskcity · Post by **minskcity** » Thu Jun 17, 2004 2:55 am

As I understand from this posts, following are correct:
INPUT:

3 0 4
0 0
0 0
10 0
0 0
5 0
10 0
11 0

4 0 2
-1 1
-1 1
-1 1
-1 1
10 10
-1 1
0 0 0

OUTPUT:

Data set 1:
Citizen at (0,0) is safe.
Citizen at (5,0) is safe.
Citizen at (10,0) is safe.
Citizen at (11,0) is neither.

Data set 2:
Citizen at (10,10) is neither.
Citizen at (-1,1) is safe.

According to the problem statement:

For purposes of this problem, a triangle consists of three non-collinear points

How can anybody be possibly safe in the first data set, if it does not contain triangles???????????

minskcity · Post by **minskcity** » Thu Jun 17, 2004 3:18 am

Just got accepted from the second try...

JUDGE IS WRONG !!!JUDGE IS WRONG !!!JUDGE IS WRONG !!!JUDGE IS WRONG !!!JUDGE IS WRONG !!!JUDGE IS WRONG !!!JUDGE IS WRONG !!!JUDGE IS WRONG !!!JUDGE IS WRONG !!!JUDGE IS WRONG !!!JUDGE IS WRONG !!!JUDGE IS WRONG !!!JUDGE IS WRONG !!!JUDGE IS WRONG !!!JUDGE IS WRONG !!!JUDGE IS WRONG !!!JUDGE IS WRONG !!!JUDGE IS WRONG !!!JUDGE IS WRONG !!!

see previos post!!!!!!

Per · Post by **Per** » Thu Nov 04, 2004 11:04 am

No, but the postscript file is wrong.
The html version has a different definition of what a triangle is.

minskcity · Post by **minskcity** » Thu Nov 04, 2004 6:17 pm

Per wrote:No, but the postscript file is wrong.
The html version has a different definition of what a triangle is.

The html version has been changed after I sent a email to the uva admin. When I was posting here, the html was wrong. (I dont even know how to open postscript on my windows...)

PS: it's good there is finally some competition for the first place in the rank list

BiK · Post by **BiK** » Mon Nov 08, 2004 5:58 pm

I am also getting constantly WA altough I read everything in the forum very carefully. I tested my convex hull algorithm also with several other problems but I get only one answer here - WA.

d91-lek · Post by **d91-lek** » Tue Nov 16, 2004 6:41 am

I had big trouble determining the case of being on the polygon. When the hull is flat and every turn is either 0 or 180 degrees, the cross product isn't enough to reject or embrace a point on the same line as the edges of the hull. See final set below. I used to get safe.

Code: Select all

Answer:

Code: Select all

Data set 1:
     Citizen at (0,0) is neither.

Data set 2:
     Citizen at (0,0) is safe.

Data set 3:
     Citizen at (0,0) is robbed. 

Data set 4:
     Citizen at (20,0) is neither.

Jan · Post by **Jan** » Tue Nov 15, 2005 10:47 pm

I haven't solved it yet... But I believe the above output set is wrong...

Input:

Code: Select all

I dont know the correct output according to the problem, But I believe the output should be ...
Output:

Code: Select all

Data set 1: 
     Citizen at (0,0) is neither.

Because There is no triangle formed by the cops though they have 3 points (0, 0), (0, 0), (0, 0). But they can't form a triangle because summation of any two sides of a triangle must be greater than the third one...

So, If you form a triangle you get three sides of length 0, 0 and 0. So, summation of any 2 sides is equal to 0 which is equal to he third one. So, there is no triangle....

But the problem states....

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.

A triangle consists of three points......so, (0, 0), (0, 0), (0, 0) can make a triangle(for this problem)? I m confused...

Thanks in advance...

OJ Board

361 - Cops and Robbers

Colinear cops...

Point in Polygon

Yet WA

Who can why my code for problem for 361 is wrong?