Description
Given a set of lines, each line is represented as `y = a * x + b`. Calculate
the number of lines in the upper-envelop and the number lines in the
lower-envelop. (You may assume that there is no three lines going through the
same point. And for any three lines, they can’t be in all parallel to each
other, but it’s possible that two lines are parallel to each other.)
# Input
There are n + 1 lines, the first line gives only one number `n`, the number of lines. Each of the following lines contains two floating numbers `a` and `b` separated by space which represent a line as `y = a * x + b`.
You can assume that 0 <= n <= 1000, and that each floating numbers
are in the range of [-100.0, 100.0].
Your code should read the input from standard input (e.g.
using functions `input()/raw_input()` in Python and `cin/scanf` in C++).
# Output
Two numbers in a line separated by space, the number of lines in the upper-envelop and the number lines in the lower-envelop.
Your code should write the output to standard output (e.g. using functions `print` in Python and `cout/printf` in C++).
# Requirement
Your algorithm should run in O(nlogn) time.
Time limtation: 5 seconds.
Memory limitation: 1.0 GB
