361 - Cops and Robbers
Moderator: Board moderators
-
- Experienced poster
- Posts: 167
- Joined: Fri Oct 19, 2001 2:00 am
- Location: Saint Petersburg, Russia
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.
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.
Colinear cops...
if there are n >= 3 cops and all n cops are colinear, can a citizen be safe?
JP
jpfarias@lcc.ufrn.br
JP
jpfarias@lcc.ufrn.br
-
- Experienced poster
- Posts: 167
- Joined: Fri Oct 19, 2001 2:00 am
- Location: Saint Petersburg, Russia
Point in Polygon
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.
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.
Yet WA
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:
And this gives me WA
Can anyone help, or should I surrender?
JP!
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
![:(](./images/smilies/icon_frown.gif)
Can anyone help, or should I surrender?
JP!
-
- New poster
- Posts: 17
- Joined: Wed Jul 17, 2002 5:00 pm
Who can why my code for problem for 361 is wrong?
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]
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]
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
)
(How I wish I had read Ivan Golubev's previous posts carefully
![:D](./images/smilies/icon_biggrin.gif)
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
As I understand from this posts, following are correct:
INPUT:
INPUT:
OUTPUT: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
According to the problem statement: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.
How can anybody be possibly safe in the first data set, if it does not contain triangles???????????For purposes of this problem, a triangle consists of three non-collinear points
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!!!!!!
![:oops:](./images/smilies/icon_redface.gif)
![:oops:](./images/smilies/icon_redface.gif)
![:evil:](./images/smilies/icon_evil.gif)
![:evil:](./images/smilies/icon_evil.gif)
![:evil:](./images/smilies/icon_evil.gif)
see previos post!!!!!!
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...)Per wrote:No, but the postscript file is wrong.
The html version has a different definition of what a triangle is.
PS: it's good there is finally some competition for the first place in the rank list
![:wink:](./images/smilies/icon_wink.gif)
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.
Answer:
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
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.
I haven't solved it yet... But I believe the above output set is wrong...
Input:
I dont know the correct output according to the problem, But I believe the output should be ...
Output:
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....
Thanks in advance...
Input:
Code: Select all
3 0 1
0 0
0 0
0 0
0 0
0 0 0
Output:
Code: Select all
Data set 1:
Citizen at (0,0) is neither.
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....
A triangle consists of three points......so, (0, 0), (0, 0), (0, 0) can make a triangle(for this problem)? I m confused...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.
Thanks in advance...
Ami ekhono shopno dekhi...
HomePage
HomePage