Solution to GCJ2015 R1A

---

Mushroom Monster

For the first method, if data[i] is greater than data[i+1] we add data[i] - data[i+1] to the answer
For the second method, we find the maximum value of data[i] - data[i+1] first, which is denoted by speed.
The maximum value means the minimum number of mushrooms Kaylin should eat in 10 seconds.
We add min(speed, data[i]) (0 <= 0 <= n - 1) to the answer.

---

Haircut

Given a time X, we can compute the number of customers who have been cut hair or is being cutting hair,
which will be denoted as F(X). If a barber finishes cutting one customer's hair at that time, we
think the next customer is not being cutting hair. Find the smallest X such that F(X) >= n by binary searching.
Then we can consider situation when X-1 minutes finished, and compute the time a barber can serve for the
next customers. Sort the the barbers by the time and find the n-F[x-1] one.

---

Logging

We can use brute force to solve the small test case.
For the large test case, imagine that a tree is on the convex hull after cutting some trees, there
must exist a line such that all the tree is on the line or lie in the same side of the line. By
enumerating all the possible lines and checking other trees position, we can cut all the trees on
one side of the line to make the trees on the line on the convex hull. From this observation we obtain
an algorithm of O(n^3). We can fix a tree and consider all the line through this tree together. Use
P[i] to denote the position of the ith tree. If P[i] is fixed, we sort all the other points by the
angle of vector P[x] - P[i]. Use Q to denote the sorted trees, we draw a line through point P[i] and
Q[0] first, which divides the trees into three classes. Then, we draw a line through point P[i] and
Q[1]. We can reuse the result of the previous drawing.