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

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

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
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:

Colinear cops...

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
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

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
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:

Point in Polygon

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
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:

Yet WA

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
New poster
Posts: 17
Joined: Wed Jul 17, 2002 5:00 pm

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

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
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:

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
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

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 :D )
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

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
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

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

Just got accepted from the second try... :oops: :oops: :evil: :evil: :evil: 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
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

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
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

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 :wink:

BiK
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm

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
New poster
Posts: 22
Joined: Thu Sep 16, 2004 2:25 am
Location: KTH, Stockholm
Contact:

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

0 2 1
0 0
0 0
0 0
0 3 1
0 0
0 0
0 0
0 0
2 3 1
-5 0
5 0
-5 0
5 0
5 0
0 0
3 0 1
0 0
10 0
-10 0
20 0
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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

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

3 0 1 
0 0 
0 0 
0 0 
0 0
0 0 0 
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...
Ami ekhono shopno dekhi...
HomePage

Post Reply

Return to “Volume 3 (300-399)”