문제
준혁이는 어느 넓은 농장에 N개의 허수아비를 발견했다.
이 농장 사람들은 1년에 몇 번 허수아비를 이용한 게임을 한다.
게임은 몇 개의 보물을 어딘가 숨겨서 찾는 것이 목적이다.
보물이 있는 위치는 N개의 허수아비들 중 2개를 골라서
이 두 허수아비를 대각선으로 하는 직사각형(각 변은 x, y축에 평행)을 만들 때,
이 사각형에 포함되는 허수아비가 없는 영역에 있을 가능성이 있다.
(단 두 점은 반드시 양의 기울기를 가지는 점으로 골라야 한다.)
준혁이는 각 허수아비의 위치가 주어질 때,
보물이 있을 수 있는 곳의 위치는 모두 몇가지인지 궁금해졌다.
여러분이 준혁이를 도와 이를 구해주자.
입력
첫 번째 줄에 허수아비의 수인 N이 주어진다. (1 ≤ N ≤ 200,000)
이어지는 N개의 줄에 허수아비의 좌표 xi, yi가 공백으로 구분되어 주어진다.
(0 ≤ xi, yi ≤ 1,000,000,000, 모든 xi값은 모두 다르며, yi값도 마찬가지다.)
출력
보물이 있을 수 있는 곳의 영역의 개수를 출력하여라.
예제1
입력
4
00
22
34
43
출력
3
입출력 예제에서는 다음과 같이 총 세개의 영역이 생긴다.
출처
20201031 집중강화학습3차6번, dennisstar,JOI SC 2014 Day3 #2