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.x > extremo.x || (p.x == extremo.x && p.y < extremo.y))
{
extremo.x = p.x;
extremo.y = p.y;
ix = i;
}
}
for (i=0;i<t;++i)
{
if (i != ix)
{
if (p.x != extremo.x)
p.ang = (double)(p.y - extremo.y)/(double)(p.x - extremo.x);
else
p.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?

[jpfarias]

Hi! I'm still having trouble with this one!!!

I've fixed my convex hull algorithm (solved problem 681!!!) but I'm still getting WA in this problem.

My approach is as follows:

If I have 2 or more cops (robbers), I try out to find the convex hull with it's coordinates so I check to see if each citizen is inside the resulting polygon, if it is on the cops convex hull, it is safe, else if it is on the robbers convex hull, then it is robbed, else it is neither!!!

I think this is the right way to solve this problem, but If I'm wrong, tell me and correct me!!!

PS: I consider the point to be inside a polygon if it is on the border of the polygon also...

PS2: Hope Brazil win the World Cup

Thanx in advance!

Jo

[Ivan Golubev]

If there 2 or less cops (robbers) then citizen cannot be safe (robbed) because cops cannot form a triangle! Raise low limit from 2 to 3 cops.

[xenon]

says:

02/01/02, Warning: When a citizen is between two cops (resp. robbers) or match one of them, it must be considered 'safe' (resp. 'robbed').

PS. But I fear boring Germany will win <Yawn>

[jpfarias]

Now I've made the lower limit = 3 but still got WA...

When it says match it wanna say x == x && y == y?

Someone had wrote in a previous topic that if a citizen is at the same place of a cop it is not safe.... Is this true?

Thanx

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