ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

USU Open Personal Contest 2010

About     Problems     Submit solution     Judge status     Standings
Contest is over

B. Explosion in a Pyramid

Time limit: 0.5 second
Memory limit: 64 MB
Lich Sandro is standing on the floor of a triangular pyramid at the point (x0, y0, 0). The vertices of the pyramid have coordinates (x1, y1, 0), (x2, y2, 0), (x3, y3, 0), (x4, y4, H). He wants to fly to the point (x0, y0, h) and create a spherical force field centered at that point. A rise to the height z takes z units of mana. Creating a field of radius r takes r units of mana. If the force field has at least one common point with the walls or floor, then the pyramid collapses. Initially Sandro has m units of mana. Is this amount sufficient to break the pyramid with a force field?


The first line contains the integers m, h, H (1 ≤ m, h, H ≤ 1000). In the following five lines, you are given the integers xi, yi, where 0 ≤ i ≤ 4 (−1000 ≤ xi, yi ≤ 1000). The point (x0, y0, h) lies strictly inside the pyramid.


Output “YES” if Sandro can break the pyramid with a force field, otherwise output “NO”.


13 6 30
6 6
0 0
0 30
30 0
0 0
11 6 30
6 6
0 0
0 30
30 0
0 0
Problem Author: Alexander Ipatov
Problem Source: XI USU Open Personal Contest (March 13, 2010)
To submit the solution for this problem go to the Problem set: 1754. Explosion in a Pyramid