Shil and Hiking
Practice
3.7 (46 votes)
Geometry
Implementation
Open
Algorithms
Approved
Medium
Problem
46% Success 647 Attempts 30 Points 1s Time Limit 256MB Memory 1024 KB Max Code

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

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:30
5 votes
Tags:
Basic MathC++Math
Points:30
4 votes
Tags:
MathematicsMediumOpenApprovedMathamatics
Points:30
3 votes
Tags:
AlgorithmsOpenApprovedMediumMathamatics