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