A super-intelligent species of coconut-eating tropical bird has decided to develop a scenic
ight path
roughly following the perimeter of the island that they inhabit. Owing to the impressive energy con-
sumption of their overdeveloped brains, these birds can only afford to
y in straight lines from one
coconut tree to the next.
The birds reasoned that they can approximate the shape of their island (from a bird's-eye view, if
you must) by imagining a rubber band that is stretched to circumscribe the island. The band is then
released so that it contracts until it makes contact with the trunks of some of the coconut trees found
on the island. The resulting shape of the elastic band thus forms straight lines between the coconut
trees it is in contact with (allowing efficient travel), whilst maintaining the additional property that
any line with endpoints inside the shape will be contained entirely within the shape. This implies that
all coconut trees will fall strictly inside the shape defined by the rubber band. rubber band The birds know the exact coordinates of each and every tree on the island. Using only this informa-
tion, they now want to calculate the number of trees required to define the shape formed by the rubber
band.
Input:
Your input consists of an arbitrary number of records, but no more than 20. Each record starts with
the integer value n, denoting the number of points in that record, followed by n pairs of real numbers
separated by white space (one or more space and/or newline characters), with 3 <= n <= 15000. Individual
coordinates are in the range [-8; 8] in both dimensions. Each number will have at most 20 digits after
the decimal point.
The input data is guaranteed to satisfy the following property: for any three points, the triangle
formed by said points will have an area of at least 10^-10. You may assume that the tree trunks are
infinitely thin.
The end of input is indicated by a line containing only the value `-1'.
What have you done, besides posting your homework assignment?
Show your code to us and pinpoint the errors you have.
We will be more than happy to help.
You need to start by thinking. How would you solve this without a computer. How would you solve it by just drawing on a piece of paper? You can't code the solution until you know how to solve it.
This sounds like a variant of the "traveling salesman" problem.
Not quite; once the question is understood, a simple drawing makes the solution obvious. The difficulty is in understanding the question, at which point the answer becomes clear and the only thing left to do is code it up.
Doing it manually with a half-dozen trees on a piece of paper reveals the solution, and the programming skill is then to automate it.
This looks like a pretty way of describing a Convex Hull to me.
ps: I wonder why they specify the max number of records of data (20), but not the max number of points per record?
ps: I wonder why they specify the max number of records of data (20), but not the max number of points per record?
The max number of points per record is stated; 15000.
You are right. I am either blind or an idiot.
J
If it was me I'd be super smart and simply hand in a piece of paper saying these birds can't be all that super intelligent. How are they supposed to break open the cocunuts? Question solved, received grade A+ for improvisation.
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.