## 361 - Cops and Robbers

Moderator: Board moderators

hi..I can't figure out the problem's description, what does "between" mean?
Or somebody can give me some test cases?
I've tried to solve this problem for a long time :~

<font size=-1>[ This Message was edited by: LittleJohn on 2002-04-01 16:21 ]</font>
LittleJohn
Learning poster

Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan

Did you read the "FIX"? Click on the "!" after the problem name. Hope that helps, haven't solved it myself yet.
Stefan Pochmann
A great helper

Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany

### Shit!

I'm sure my algorithm is fine but only got WA.....

I'm using graham scan and so...

There is any trick test case?

If u can give me some input/output I will be thankful!

Jo
jpfarias
Learning poster

Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil

Do not use floating point in this problem, there can be precision errors. Also a small I/O.

Input:
3 3 2
0 0
10 0
0 10
20 20
20 0
0 20
5 5
15 15

3 3 1
0 0
10 0
0 10
20 20
20 0
0 20
40 40

3 3 4
0 0
1 2
3 3
4 0
4 3
6 3
0 1
2 3
1 0
2 1

3 1 4
4 -1
4 -1
6 2
3 2
3 2
5 0
5 1
6 2

3 0 1
14 5
14 22
11 17
14 6

0 0 0

Output:
Data set 1:
Citizen at (5,5) is safe.
Citizen at (15,15) is robbed.

Data set 2:
Citizen at (40,40) is neither.

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

Data set 4:
Citizen at (3,2) is neither.
Citizen at (5,0) is neither.
Citizen at (5,1) is neither.
Citizen at (6,2) is neither.

Data set 5:
Citizen at (14,6) is safe.
Ivan Golubev
Experienced poster

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

Hi!

Had you read the fix? It says that if you are between two cops (or robbers) you're safe (or robbed). And also if you're over the cop (or the robber).

Did u solved this problem? If u had solved could u analyse my code or send me yours?

[cpp]

#include <iostream.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define ABS(x) ((x)<0?-(x):(x))
// points
struct ponto {
int x;
int y;
double ang;
};
// cops robs citizens
ponto conv_hull[210];

double PI;

double angle(ponto p1, ponto p2)
{
double res;
if (p1.x == p2.x)
return PI/2;
if (p1.y == p2.y)
return 0.0;
res = atan2((double)(p1.y-p2.y),(double)(p1.x-p2.x));
if (res < 0)
return res+PI;
return res;
}

double angle3(ponto p1, ponto p2, ponto p3)
{
double a1, a2;
a1 = angle(p1,p2);
a2 = angle(p2,p3);
return fabs(a1-a2);
}

ponto extremo = { -1001, 1001 };

int comp_ang(const void *a1, const void *a2)
{
ponto *p1 = (ponto *)a1, *p2 = (ponto *)a2;
if (p1->ang < p2->ang)
return -1;
else if (p1->ang > p2->ang)
return 1;
double d1 = (extremo.x - p1->x)*(extremo.x-p1->x) + (extremo.y-p1->y)*(extremo.y-p1->y);
double d2 = (extremo.x - p2->x)*(extremo.x-p2->x) + (extremo.y-p2->y)*(extremo.y-p2->y);
if ( d1 - d2 > 0)
return 1;
else if (d2 - d1 > 0)
return -1;
return 0;
}

void simple_polygon(ponto *p, int t)
{
int i, ix;
for (i=0;i<t;++i)
{
if (p[i].x > extremo.x || (p[i].x == extremo.x && p[i].y < extremo.y))
{
extremo.x = p[i].x;
extremo.y = p[i].y;
ix = i;
}
}
for (i=0;i<t;++i)
{
if (i != ix)
{
if (p[i].x != extremo.x)
p[i].ang = (double)(p[i].y - extremo.y)/(double)(p[i].x - extremo.x);
else
p[i].ang = -99999;
}
else
p[i].ang = -99999.9;
}
qsort(p,t,sizeof(ponto),comp_ang);
}

// Tells if a point is inside of a polygon
bool dentro(ponto p1, ponto *p, int n) {
double x1,y1,x2,y2,x,y;
int cont=0;
int i1=0,i2;
for(int i=0;i<n;i++) {
if(p[i].x==p1.x && p[i].y == p1.y)
return true;
if(p[i].x==p1.x && p[i+1].x==p1.x)
if((p[i].y>p1.y && p[i+1].y<p1.y) || (p[i].y<p1.y && p[i+1].y>p1.y))
return true;
}
while(i1<n)
{

while(p[i1].x==p1.x && p[i1].y < p1.y && i1<n)
i1++;
if(i1==n)
break;
i2=i1+1;
while(p[i2].x==p1.x && p[i2].y < p1.y)
{
int ii2 = i2;
i2=(i2+1)%(n+1);
while (p[i1].y > p1.y && p[i2].y>p1.y)
{
i2=(i2+1)%(n+1);
if (i2 == ii2)
break;
}
if (i2 == ii2)
break;
}

if ((p[i1].x < p1.x && p[i2].x > p1.x) || (p[i1].x > p1.x && p[i2].x < p1.x))
{
y1 = (double)p[i1].y; y2 = (double)p[i2].y;
x1 = (double)p[i1].x; x2 = (double)p[i2].x;
x = (double)p1.x;
if (x2!=x1)
{
y = (((y2-y1)*x)+(y1*x2-x1*y2))/(x2-x1);
}
else
continue;
if (ABS(y-(double)p1.y)<0.00001)
return true;
if (y < (double)p1.y)
cont++;
}
i1++;
}
if (cont%2)
return true;
return false;
}

bool colinear(ponto * p) {
double tmp1,tmp2;
int p1=0, p2=0;
if (p[0].x == p[1].x && p[0].y == p[1].y)
return true;
if (p[0].x == p[2].x && p[0].y == p[2].y)
return true;
if (p[1].y == p[2].y && p[1].x == p[2].x)
return true;
if (p[0].x - p[1].x)
tmp1=(double)(p[0].y-p[1].y)/(double)(p[0].x-p[1].x);
else
p1 = 1;

if (p[0].x - p[2].x)
tmp2=(double)(p[0].y-p[2].y)/(double)(p[0].x-p[2].x);
else
p2 = 1;
if (p1 && p2)
return true;
if (p1 && !p2)
return false;
if (p2 && !p1)
return false;
if(ABS(tmp1-tmp2)<0.000001)
return true;
return false;
}

int chtam;

void graham_scan(ponto *p, int t)
{
int m, k;
simple_polygon(p,t);
chtam = 3;
m = 2;
conv_hull[0].x = p[0].x; conv_hull[0].y = p[0].y;
conv_hull[1].x = p[1].x; conv_hull[1].y = p[1].y;
conv_hull[2].x = p[2].x; conv_hull[2].y = p[2].y;
for (k=3;k<t;++k)
{
while (angle3(conv_hull[m-1],conv_hull[m],p[k])>=PI && m>0)
--m;
++m;
conv_hull[m].x = p[k].x; conv_hull[m].y = p[k].y;
}
chtam = m+1;

}

int main() {
int p,l,c,d=0;
int stat[200];
PI = 2*acos(0);
while(cin >> p >> l >> c, p || l || c) {
cout << "Data set " << ++d << ':' << endl;
for(int i=0;i<p;i++)
{
cin >> policia[i].x >> policia[i].y;
policia[i].x += 500;
policia[i].y += 500;
}
for(int i=0;i<l;i++)
{
}
for(int i=0;i<c;i++)
{
}
int pcol = 1;
for (int i=0;i<p-2;++i)
if (!colinear(policia+i)) {
pcol = 0;
break;
}
if (pcol)
p = 0;
if (p>2)
{
graham_scan(policia,p);
memcpy(policia,conv_hull,sizeof(ponto)*chtam);
p = chtam;
}
int lcol = 1;
for (int i=0;i<l-2;++i)
lcol = 0;
break;
}
if (lcol)
l = 0;
if (l>2)
{
l = chtam;
}

policia[p].x = policia[0].x;
policia[p].y = policia[0].y;

for (int i=0;i<c;++i)
stat[i]=0;
for (int i=0;i<c;++i)
{
stat[i] = 1;
stat[i] = 2;
}

for(int i=0;i<c;i++) {
cout << "Citizen at (" << cidadao[i].x-500 << "," << cidadao[i].y-500 << ") is ";
switch(stat[i]) {
case 0:
cout << "neither.\n";
break;
case 1:
cout << "safe.\n";
break;
case 2:
cout << "robbed.\n";
}
}
cout << endl;
}
return 0;
}

[/cpp]

I think the error is in the function that tells if a point is inside of a polygon cause it's was not much tested...

Jo
jpfarias
Learning poster

Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil

### Re: Is your output ok?

jpfarias wrote:Had you read the fix? It says that if you are between two cops (or robbers) you're safe (or robbed). And also if you're over the cop (or the robber).

I've solved this problem about year ago. In that time there was another message under fix sign.
jpfarias wrote:Did u solved this problem? If u had solved could u analyse my code or send me yours?

As I've already said do not use floating point. The input values given as integers so the whole solution can be written using only integers. Floating point can produce precision errors so why to use it?..

About your solution: it's definitely lazy to me to debug your code (especially during Football World Cup ) but here is some ideas:
1. If there less than 3 cops (robbers) then citizen can't be safe.
2. If citizen coordinates lays on line produces by two cops it's safe (as under fix sign).
3. If citizen coordinates are the same as cop coordinates it isn't safe! It differs from fix sign comment but my accepted solution used this assumption.
4. If citizen inside triangle it's safe (of course).

Firstly I've used convex hull but then I've switched to stupid brute-force, just trying all possible triangles one by one. This gives me AC.

I think the error is in the function that tells if a point is inside of a polygon cause it's was not much tested...

If you're suspect that there can be a bug why not to test it one more time?
Ivan Golubev
Experienced poster

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

### Re: Is your output ok?

Ivan Golubev wrote:
jpfarias wrote:Had you read the fix? It says that if you are between two cops (or robbers) you're safe (or robbed). And also if you're over the cop (or the robber).

I've solved this problem about year ago. In that time there was another message under fix sign.

Hmm...... It's funny, but I couldn't find you in a list of people who was gaved by AC.
New poster

Posts: 2
Joined: Tue Apr 09, 2002 4:32 pm
Location: Russia, Ekaterinburg

### Re: Is your output ok?

Ivan Golubev wrote:
jpfarias wrote:Had you read the fix? It says that if you are between two cops (or robbers) you're safe (or robbed). And also if you're over the cop (or the robber).

I've solved this problem about year ago. In that time there was another message under fix sign.

Hmm...... It's funny, but I couldn't find you in a list of people who was gaved by AC.

Check out one more time, I'm still in ranklist (with the worst time but I don't want to resolve this problem).
Ivan Golubev
Experienced poster

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

### Hi!

Hi!

I also have a problem with this task..

I have solved 109 ( Scud Busters ) and I think that this is quite a similar problem....

Could anyone ( who get Accepted tell me :
If a citizen is in the same place as cop is he counted safe or not ??
and if he is on the line ??

3 0 3
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

cyfra
Experienced poster

Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

cyfra wrote:If a citizen is in the same place as cop is he counted safe or not ??
and if he is on the line ??
In both cases citizen is safe. I've wasted about ten submissions to figure out this problem and everything looks fine now.

Output (as I can understand first line of your input must be 3 0 4 not 3 0 3):
Code: Select all
`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.`
Ivan Golubev
Experienced poster

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

Is it correct :

3 1 4
4 -1
4 -1
6 2
3 2
3 2
5 0
5 1
6 2

0 0 0

and output

Data set 4:
Citizen at (3,2) is neither.
Citizen at (5,0) is neither.
Citizen at (5,1) is neither.
Citizen at (6,2) is neither.

( I think that here should be Citizen at (6,2) is safe. )

cyfra
Experienced poster

Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

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.
Ivan Golubev
Experienced poster

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

### Colinear cops...

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

JP
jpfarias@lcc.ufrn.br
jpfarias
Learning poster

Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil

jpfarias wrote:if there are n >= 3 cops and all n cops are colinear, can a citizen be safe?
Yes, it can be safe.
Ivan Golubev
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).

jpfarias
Learning poster

Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil

Next