Shil and Hiking

3.7

46 votes
Geometry, Implementation, Open, Algorithms, Approved, Medium
Problem

Shil decided to go for hill climbing on this weekend, but he doesn't have the map of all the hills. However, he's smart enough to make his own map.

There are N hills arranged on a line, each in the form of a vertical line segment with one endpoint on the ground. The hills are numbered with numbers from 1 to N from left to right. The ith hill stands at the position xi with its top at height yi.

A pair (a, b) ( where a < b ) is called beautiful if and only if Shil will be able to see the peak of bth hill standing on the top of ath hill.

In order to make his own map, Shil needs total number of beautiful pairs. As Shil is not a very good programmer, he asks for your help.

Assume that Shil's height is very small as compared to the height of hills. (Really!) Thus, we can assume that Shil's eyes are exactly at the height of peak if he is standing at peak of some hill.

You can also assume that Shil is able to see peak of certain hills if distance between peak and Shil's sight is less than 10-4.

Input format:
The first line of the input contains a single integer N , the number of hills. The next N lines describe the hills. The ith of them contains two space-separated integers xi, yi , the position and the height of the ith hill. The hills are given in the ascending order of xi, i.e., xi < xj for i < j.

Output format:
Print the total number of beautiful pairs.

Constraints:
2 ≤ N ≤ 1000
1 ≤ xi , yi ≤ 109

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

All the beautiful pairs are (1,2),(1,3),(2,3),(3,4)

Editor Image

?