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

LittleJohn
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan
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
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
Did you read the "FIX"? Click on the "!" after the problem name. Hope that helps, haven't solved it myself yet.

jpfarias
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:

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

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia
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
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:

Is your output ok?

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;

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.x == p.x && p.y == p.y)
return true;
if (p.x == p.x && p.y == p.y)
return true;
if (p.y == p.y && p.x == p.x)
return true;
if (p.x - p.x)
tmp1=(double)(p.y-p.y)/(double)(p.x-p.x);
else
p1 = 1;

if (p.x - p.x)
tmp2=(double)(p.y-p.y)/(double)(p.x-p.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.x = p.x; conv_hull.y = p.y;
conv_hull.x = p.x; conv_hull.y = p.y;
conv_hull.x = p.x; conv_hull.y = p.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;
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.x;
policia[p].y = policia.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;
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

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

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?

jpfarias
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:

361 - Cops and Robbers

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 Jo

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia
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
Learning poster
Posts: 100
Joined: Fri May 24, 2002 10:35 am
Location: Scheveningen, Holland 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
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:

Still getting WA

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

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.

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.
Check out one more time, I'm still in ranklist (with the worst time but I don't want to resolve this problem).

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

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

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

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland
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. )