문제 설명
캠핑
무지를 돌보느라 지친 콘은 한적한 시골의 한 캠핑장에 놀러 갔다. 캠핑장은 텐트를 칠 수 있는 넓은 평지를 제공하고 있는데, 이 평지에는 이미 캠핑장에서 설치해 놓은 n
개의 쐐기가 박혀 있다. 캠핑장 이용 고객은 이 쐐기들 중 한 쌍을 골라 다음과 같은 조건을 만족하도록 텐트를 설치해야 한다.
- 텐트는 직사각형 형태여야 한다.
- 텐트의 네 면이 정확하게 동, 서, 남, 북을 향해야 한다.
- 대각에 위치하는 텐트의 두 꼭짓점이 정확하게 선택한 두 개의 쐐기에 위치해야 한다.
- 텐트가 점유하는 직사각형 영역의 넓이는 0보다는 커야 한다.
- 텐트가 점유하는 직사각형 영역 내부에 다른 쐐기를 포함하면 안 된다. (다른 쐐기가 경계에 위치하는 경우는 허용함)
캠핑장에서는 위와 같은 조건을 만족하는 위치라면 어디든 고객이 텐트를 설치할 수 있도록 정확한 크기의 텐트를 모두 구비하여 대여해준다고 한다.
당신은 위와 같은 조건을 만족하는 텐트를 설치할 수 있는 쐐기의 쌍의 개수는 총 몇 가지가 될지 궁금해졌다.
n
개의 쐐기의 위치가 좌표로 주어질 때, 위의 조건을 만족하는 쐐기의 쌍의 개수를 계산하는 프로그램을 작성하시오. 단, 동서 방향은 x축, 남북 방향은 y축과 평행하다고 가정한다.
입력 형식
입력은 쐐기의 개수를 의미하는 정수 n
과, n × 2
크기의 2차원 배열 data
로 주어지며, 배열의 각 행은 캠핑장에 설치된 쐐기의 x좌표와 y좌표를 의미한다. 제한 조건은 다음과 같다.
2 <= n <= 5,000
n
개의 쐐기는 모두 x좌표0
이상2^31-1
이하, y좌표0
이상2^31-1
이하에 위치한다.- 입력되는
n
개의 쐐기 중 x좌표와 y좌표가 모두 같은 경우는 없다.
출력 형식
입력에 주어진 각 케이스에 대해 가능한 텐트의 쐐기의 쌍의 개수를 정수 형태로 리턴한다.
예제 입출력
n | data | answer |
---|---|---|
4 | [[0, 0], [1, 1], [0, 2], [2, 0]] | 3 |
예제에 대한 설명
예제에는 총 4개의 쐐기가 있으며 이 중 (0,0)-(1,1), (0,2)-(1,1), (1,1)-(2,0)의 세 가지 위치에만 텐트를 설치할 수 있다. (0,0)-(0,2)와 (0,0)-(2,0)의 경우에는 직사각형 영역의 넓이가 0이 되기 때문에 조건을 만족하지 못하며, (0,2)-(2,0)의 경우 (1,1) 위치의 쐐기가 직사각형의 내부에 포함되므로 조건을 만족하지 못한다.