143 - Orchard Trees

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

Moderator: Board moderators

Should the judge tell us which test cases are messing us up?

Total votes: 33

New poster
Posts: 22
Joined: Tue Jun 19, 2007 3:18 am

Re: 143 - Orchard Trees

Post by rafastv » Thu Jul 20, 2017 11:44 pm

Hi, there, some tips for you if you suffered with this problem.

1) You must consider lines and points too besides triangles.

2) Pay attention to PRECISION of your floating-point variables, 1e-9 is enough.

3) Try at first solving the problem through brute force and when you are able, only then, solve it through a more refined method.

4) Many of the samples here are not valid input, remember the description of the problem there is no input like 0.999999999999 or something like that, but you must be able to handle such a number if it appears in your computations. The worst number I've found for point inside triangle test was something like U -0.00000000000000013366500403377148334747596430321874 and V 0.944444444444445.

Good luck!

Post Reply

Return to “Volume 1 (100-199)”