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

d91-lek
New poster
Posts: 22
Joined: Thu Sep 16, 2004 2:25 am
Location: KTH, Stockholm
Contact:

Post by d91-lek » Wed Nov 16, 2005 5:45 pm

Jan,

very clever of you to think of the triangle inequality, the only criteria for a triangle. However, you have it wrong! The sum of any two sides must be greater than or equal to the third. We simply must allow for triangles with no area. (0,0) - (0,0) - (0,0) is indeed a triangle. The only point inside it being (0,0).

I hope this helps. If I'm not right with the geometry, atleast I have figured out the rules for this particular problem and will try to answer further questions should you have any,

/Linus

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Wed Nov 16, 2005 9:22 pm

Thanks d91-lek for answering...

I think you are wrong. suppose there are three points, (0,0), (1,0) and (2,0), So summation of any two sides are less or equal than the third...But These three form a line not a triangle.....

And You will find the proof in any higher school mathematics book. I m getting WA in this problem.... Can you tell me why the output of your second test case is safe....

Thank you again...
Ami ekhono shopno dekhi...
HomePage

d91-lek
New poster
Posts: 22
Joined: Thu Sep 16, 2004 2:25 am
Location: KTH, Stockholm
Contact:

Post by d91-lek » Fri Nov 18, 2005 4:30 am

Sorry about the delay,

but we seem to have so fundamentally different opinions on triangles I had to go read the problem specificaton and a math book or two. I am very weak at debating so I'll try Socrates' method of reasoning on your line until we run into contradictions, or in this case, ugliness.

A triangle is a polygon with exactly three sides and it is completely determined by three points, that much we agree on. Now, you additionally hold these three points must all be distinct, no two may coincide, and furthermore, they must not lie on a line. Or, simpler, a triangle must have area > 0.

We can let the area be as close to zero as we like, but in limes it is not a triangle anymore, just an overspecified line or point. For example the trigonometric triangle inside the unit circle when the angle is n*pi/2, for all n. But this is ugly, don't you agree? A lot of work and for what? Just to stop a few three sided polygons which happen to be drawn as a line or point from being called triangles? To able to keep the intuitive, mental picture of a canonical triangle as we all learnt as children in school?

No math book I have looked in forbids the sides of a triangle to be zero. On the contrary they formulate the Triangle Inequality like this:
|x + y| <= |x| + |y|, x, y are vectors, |.| a norm and + is vector addition,
or like this,
m(f,h) <= m(f,g) + m(g,h), f, g, h are points and m(.,.) is a measure (dist, cost).
In words, no side of a triangle is longer than the sum of the other two or a deviation from the straight line can't be shorter than that line . And, as you pointed out, this follows by proof from Euclidean geometry. But in measure theory, dealing with arbitrary sets and measures on them, the Triangle Inequality is taken as an axiom.

All I am saying is that antique and modern mathematics will not hesitate to call ANY three sided polygon a triangle. It is the simplest, sanest way. Three points? A triangle! If, of course, it is your intention to handle them as a polygon. And this is the position taken by problem 361. A triangle of cops can be three of them with identical coordinates. Aren't all problems on Valladolid like this? Full of extreme cases in the test data?

The problem statement says citizens on the boundary of triangles are considered inside. Triangles without area have only boundary, if you are willing to call even single points a boundary. (Still that single point is covered by the pointsized triangle and is therefore covering any citizen in that point.)

Now all you have to do is to carry with you this no area-thinking to convex hulls, which are just polygons of higher degree than three and which are, of course, convex.

I stop here, for I must go to bed in order to be able to bake a French chocolate cake tomorrow for my birthday party on Saturday. Once again, I hope I didn't just make a fool of myself,


Linus

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sat Nov 19, 2005 6:22 pm

Happy Birthday Linus.... Many many happy returns of the day......

And thanks for your beautiful explanation....

I m still getting WA in this problem... Can you tell me when the input is..

Input:

Code: Select all

0 2 1 
0 0 
0 0 
0 0 
0 3 1 
0 0 
0 0 
0 0 
0 0 
2 3 1 
-5 0 
5 0 
-5 0 
5 0 
5 0 
0 0 
3 0 1 
0 0
Output:

Code: Select all

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

Data set 2: 
     Citizen at (0,0) is safe. 

Data set 3: 
     Citizen at (0,0) is robbed. 

Data set 4: 
     Citizen at (20,0) is neither. 
Why the second case is 'safe'??Shouldn't it be 'robbed'??....

Thanks again....
Ami ekhono shopno dekhi...
HomePage

d91-lek
New poster
Posts: 22
Joined: Thu Sep 16, 2004 2:25 am
Location: KTH, Stockholm
Contact:

Post by d91-lek » Sat Nov 19, 2005 11:21 pm

>> Why the second case is 'safe'??Shouldn't it be 'robbed'??....

Yes, it should be 'robbed'. Quite right of you. It is very shameful of me to put out incorrect test data. Feel free to repost the entire set with correct answer if you like.

BTW, I got quite a lot of presents. Especially a warm, red sweater from mom that will enable me to stay up all nights answering questions on this forum.

/Linus

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Tue Nov 22, 2005 1:18 pm

Thats great that you have got some gifts... :wink:

Can you post some I/O please....

Thanks in advance...
Ami ekhono shopno dekhi...
HomePage

d91-lek
New poster
Posts: 22
Joined: Thu Sep 16, 2004 2:25 am
Location: KTH, Stockholm
Contact:

Post by d91-lek » Wed Nov 23, 2005 4:03 pm

''Can you post some I/O please.... ''

I have lost touch with this problem so I don't remember what situations are crucial. But I have my program to test-run input if you are unsure what the correct answer should be. (If I can get it to compile again, seems to be problems with using std with the new gcc.)

So, please, if you have any input, post them and I can put them through the program and post the answer.

/Linus

PS. The red sweater has too short arms, but I'm getting it changed for a bigger model. It is your hands that gets cold during the nights at the keyboard.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Mon Dec 05, 2005 9:23 pm

Finally got Accepted :D ... Thanks...
Ami ekhono shopno dekhi...
HomePage

mhulboj
New poster
Posts: 4
Joined: Fri Jun 10, 2005 2:02 pm

Post by mhulboj » Sat Dec 09, 2006 8:19 pm

Hello,
I have written the code that implements finding of convex hulls (AM method) and then determines whether the point is inside it or outside it. Could someone provide some more sample input, because for the one provided in the task and in this thread and some examples generated by hand the results are ok (and I've tripple checked the formatting of the output).

Regards,
Milosz

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sun Dec 10, 2006 5:55 am

Check the samples...

Input:

Code: Select all

4 4 10
0 0
20 0
0 20
20 20
10 -10
10 30
15 -10
15 30
1 1
0 0
20 19
12 12
10 22
10 31
10 20
-1 -1
15 21
15 20
0 0 0
Output:

Code: Select all

Data set 1:
     Citizen at (1,1) is safe.
     Citizen at (0,0) is safe.
     Citizen at (20,19) is safe.
     Citizen at (12,12) is safe.
     Citizen at (10,22) is robbed.
     Citizen at (10,31) is neither.
     Citizen at (10,20) is safe.
     Citizen at (-1,-1) is neither.
     Citizen at (15,21) is robbed.
     Citizen at (15,20) is safe.

Hope these help.
Ami ekhono shopno dekhi...
HomePage

mhulboj
New poster
Posts: 4
Joined: Fri Jun 10, 2005 2:02 pm

Post by mhulboj » Sun Dec 10, 2006 11:25 am

Thanks,
This output was OK, but I've tried few more manually generated and found an awfully stupid copy/paste bug in my code. After fixing got AC.
And for those seeking solution be sure to handle these cases properly:

Code: Select all

2 0 1
0 0
0 0
0 0
3 0 1
0 0
0 0
0 0
0 0
3 0 1
-2 0
2 0
0 0
1 0
3 0 1
0 -2
0 2
0 1
0 -1

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Mon Jan 29, 2007 8:16 am

Keep getting WA...
What sould be the output for mhulboj's testcase?

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Mon Jan 29, 2007 8:46 am

For his input (added 3 0's at the end), my freshly AC program outputs:

Code: Select all

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

Data set 2:
     Citizen at (0,0) is safe.

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

Data set 4:
     Citizen at (0,-1) is safe.


User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Tue Jan 30, 2007 6:46 am

Thanks, Darko. It seems that I'm handling them well.

Is there any other tricky test case ?

Thanks in advance.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Tue Jan 30, 2007 8:11 am

I don't have any special cases - I just find convex hulls if there are more than 2 points, if not, I ignore them (note that "convex hull" might contain less than 3 points). Maybe it is your point-in-polygon? I first check if the "other" point coincides with a vertex of the polygon, then, if not, I check if it is on an edge and then if it is inside. I guess once you have a tested code to do it, it should be straightforward.

Post Reply

Return to “Volume 3 (300-399)”