361 - Cops and Robbers

[d91-lek]

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]

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

[d91-lek]

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]

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

[d91-lek]

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

Thats great that you have got some gifts...

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

Thanks in advance...

[d91-lek]

''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]

Finally got Accepted ... Thanks...

[mhulboj]

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]

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.

[mhulboj]

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

[rio]

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

[Darko]

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.

[rio]

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

Is there any other tricky test case ?

Thanks in advance.

[Darko]

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.