11334 - Antenna in the Cinoc Mountains

[Lomir]

Maybe somebody have some good testcases?

My algorithm work like this:
I make a plane at cone center that is penperdicular to xOy and our looking ray.
Then i am looking to a point of ray and plane intersection.
If this point is in segment interval, I check if its distance to a cone center axis is lesser then cone distance to its own size at height of the point.

If the distance is less, then ray is intersected by a cone.

Any good ideas or tests?

[sclo]

I'm struggling with this one too.

[baodog]

Here is what I did to get ac. There are other ways also probably.

1) Use exact intersections to be safe. Solve the quadrics.

http://www.siggraph.org/education/mater ... inter4.htm

2) Handle Many Special Situations

a) Either Tower Have height 0 --> No, because the line touches
the ground (territories as in the problem). This is trickiest case.

b) Handle situation where height of cones is 0 and/or radius is 0.

c) Touching situations

3) Use long double, and small EPS.

[Robert Gerbicz]

The problem statment is wrong.

Code: Select all

Each of the next k  lines contains four positive, integer numbers xm , ym , hm  and rm , 0<=xm, ym, hm, rm<=10000 

But 0 isn't positive number! The problemsetter sholud really check out his third grade math book. And also his geography book: how do you call something a mountain if its height is zero?! Has he/she ever seen a mountain or a tower?

What are you doing if the cone's radius is 0 ? I'm currently skip these mountains in the code. Is it good?

[Vendetta]

remember not to touch the ground (or be in the ground)

[Anders]

There are a lot of things with this problem that I find difficult to understand. I would be happy if someone could help me. (I am a hurry, and should complete this task no later than Monday 25th as it is part of my homework in a course. I have already submitted a solution, which was judged WA.)

For example:

1. Can a tower stand on a mountain?
2. If a tower can stand on a mountain, should the height of the top be added to the height of the mountain at that point?
3. If the height should not be added, can the tower top be inside the mountain? Can it be on the surface?
4. Can a mountain stand on another mountain?
5. If so, are the heights to be added on that coordinate, or does only the highest count?
6. Can the towers stand on the same coordinate?
7. If they can stand on the same coordinate, is one of them supposed to be on top of the other? In that case, which is on the top?
8. If they can stand on the same coordinate, are they considered to have a free line of sight (assuming they are not within a mountain), or are the towers themselves blocking?
9. If they can stand on the same coordinate, would there be any difference if the towers are of the same height?

Thank you!

[andmej]

I haven't been able to get Accepted yet, but with assertions I discovered the following:

Can a tower stand on a mountain?

Yes. The first sample test case shows this.

If a tower can stand on a mountain, should the height of the top be added to the height of the mountain at that point?

No. You are given the coordinates of the tower's top, so this mean that you should not add the height of the mountain below it. Just assume the tower is shorter but since it's standing on the mountain it reaches the point you are given.

If the height should not be added, can the tower top be inside the mountain? Can it be on the surface?

Yes, it can be completely inside the mountain or on the surface.

Can a mountain stand on another mountain?

All mountains have different centers, but it is still possible that two mountains intersect.

Can the towers stand on the same coordinate?

No, there are no test cases like this.


Also, all mountains have positive radius and height.