361 - Cops and Robbers

[LittleJohn]

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>

[Stefan Pochmann]

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

[jpfarias]

Can someone give any hints about this problem?
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!

Thanx in advance!

Jo

[Ivan Golubev]

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.

[jpfarias]

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 policia[210], ladrao[210], cidadao[210];
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++)
{
cin >> ladrao[i].x >> ladrao[i].y;
ladrao[i].x += 500;
ladrao[i].y += 500;
}
for(int i=0;i<c;i++)
{
cin >> cidadao[i].x >> cidadao[i].y;
cidadao[i].x += 500;
cidadao[i].y+=500;
}
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)
if (!colinear(ladrao+i)) {
lcol = 0;
break;
}
if (lcol)
l = 0;
if (l>2)
{
graham_scan(ladrao,l);
memcpy(ladrao,conv_hull,sizeof(ponto)*chtam);
l = chtam;
}

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

ladrao[l].x = ladrao[0].x;
ladrao[l].y = ladrao[0].y;
for (int i=0;i<c;++i)
stat[i]=0;
for (int i=0;i<c;++i)
{
if (p && dentro(cidadao[i],policia,p))
stat[i] = 1;
else if (l && dentro(cidadao[i],ladrao,l))
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...

Thanx in advance!
Jo

[Ivan Golubev]

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.

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?

[Den Raskovalov]

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.

[Ivan Golubev]

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).

[cyfra]

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 ??

Please write your outputs for such test data:

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

Thanks in advance

[Ivan Golubev]

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.


[cyfra]

And what about your previous aswers for inputs ??

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. )

What about this ??

[Ivan Golubev]

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]

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

JP
jpfarias@lcc.ufrn.br

[Ivan Golubev]

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

Yes, it can be safe.

[jpfarias]

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.