Cafebazaar's Chess Tournament
Time limit2sMemory limit512 MB
Given n players each with an opening and ending skill, count how many distinct tournament scores a new player with freely chosen distinct skills can achieve.
- Level
Hard8 of 10
- Topics
- Geometry, Sorting, Binary search, Math
- Solved
- No attempts yet
Problem
Ali hosts a yearly chess tournament for CafeBazaar's Shab-e Yalda festival. In a chess tournament, each pair of participants play a game against each other exactly once. Players earn one point for a win, half a point for a draw, and no points for a loss toward their tournament score.
Danial has built a system to predict the result of Ali's tournament. Based on experience, he has assigned an opening skill and an ending skill to each of the n participants. For the i-th participant, let us denote the former with and the latter with . In a game between the i-th and j-th participants, Danial decides the result of the game according to the following rules.
- If and , then the i-th participant wins the game.
- If and , then the j-th participant wins the game.
- Otherwise, the game ends in a draw.
To make the tournament more exciting, Ali wants to invite Danial to join the other n participants in the tournament. Danial has no prior experience in chess, so he decides to practice for the tournament. Based on the amount of training, Danial can end up with any opening and ending skill. However, Danial has promised Ali that he will train so that his opening skill is different from the opening skill of the other participants. He will also keep his ending skill different from the ending skill of the other participants.
For his advertisement campaign, Ali wants to know the number of distinct possible final scores that Danial might get based on the rules above. For example, Danial can achieve the scores 0, 1.5, 2.5, 3, 4, and 5 in the sample. The score 3, for instance, is obtained by setting both Danial's opening and ending skills to 1.5. Since Ali and all other CafeBazaar programmers are busy planning the event, he has turned to you for help. Write a program to calculate this value.
Input
The first line of the input contains a single integer , the number of participants. ()
The i-th of the next lines contains two integers and , the opening and ending skills of the i-th participant, respectively. ()
The limits for opening and ending skills do not apply to Danial's opening and ending skills. More specifically, Danial's opening and ending skills can be any real numbers.
Output
In the only line of the output, print the number of distinct possible final scores for Danial.