361 - Cops and Robbers
Moderator: Board moderators
-
- Learning poster
- Posts: 83
- Joined: Wed Feb 27, 2002 2:00 am
- Location: Taiwan
-
- A great helper
- Posts: 284
- Joined: Thu Feb 28, 2002 2:00 am
- Location: Germany
- Contact:
Shit!
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
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
-
- 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.
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.
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 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
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
-
- Experienced poster
- Posts: 167
- Joined: Fri Oct 19, 2001 2:00 am
- Location: Saint Petersburg, Russia
Re: Is your output ok?
I've solved this problem about year ago. In that time there was another message under fix sign.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).
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?..jpfarias wrote:Did u solved this problem? If u had solved could u analyse my code or send me yours?
About your solution: it's definitely lazy to me to debug your code (especially during Football World Cup
![;-)](./images/smilies/icon_wink.gif)
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.
If you're suspect that there can be a bug why not to test it one more time?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...
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![;)](./images/smilies/icon_wink.gif)
Thanx in advance!
Jo
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
![;)](./images/smilies/icon_wink.gif)
Thanx in advance!
Jo
-
- Experienced poster
- Posts: 167
- Joined: Fri Oct 19, 2001 2:00 am
- Location: Saint Petersburg, Russia
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
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?
Hmm...... It's funny, but I couldn't find you in a list of people who was gaved by AC.Ivan Golubev wrote:I've solved this problem about year ago. In that time there was another message under fix sign.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).
-
- Experienced poster
- Posts: 167
- Joined: Fri Oct 19, 2001 2:00 am
- Location: Saint Petersburg, Russia
Re: Is your output ok?
Check out one more time, I'm still in ranklist (with the worst time but I don't want to resolve this problem).Den Raskovalov wrote:Hmm...... It's funny, but I couldn't find you in a list of people who was gaved by AC.Ivan Golubev wrote:I've solved this problem about year ago. In that time there was another message under fix sign.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).
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:
![:wink:](./images/smilies/icon_wink.gif)
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
![:D](./images/smilies/icon_biggrin.gif)
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:
Thanks in advance3 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
![:wink:](./images/smilies/icon_wink.gif)
-
- Experienced poster
- Posts: 167
- Joined: Fri Oct 19, 2001 2:00 am
- Location: Saint Petersburg, Russia
In both cases citizen is safe. I've wasted about ten submissions to figure out this problem and everything looks fine now.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 ??
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.
And what about your previous aswers for inputs ??
Is it correct :
What about this ??
Is it correct :
and output3 1 4
4 -1
4 -1
6 2
3 2
3 2
5 0
5 1
6 2
0 0 0
( I think that here should be Citizen at (6,2) is safe. )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.
What about this ??