11334 - Antenna in the Cinoc Mountains

All about problems in Volume 113. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Lomir
New poster
Posts: 19
Joined: Mon Sep 17, 2007 10:05 pm
Contact:

11334 - Antenna in the Cinoc Mountains

Post by 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
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo »

I'm struggling with this one too.

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

Post by 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
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Post by 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
New poster
Posts: 3
Joined: Fri Nov 09, 2007 1:07 pm

Post by Vendetta »

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

Anders
New poster
Posts: 6
Joined: Mon Jan 12, 2004 8:09 am
Location: Russia
Contact:

Clarification request

Post by 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
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Re: 11334 - Antenna in the Cinoc Mountains

Post by 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.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

Post Reply

Return to “Volume 113 (11300-11399)”