Exhibition
시간 제한2초메모리 제한512 MB
x좌표와 y좌표가 각각 1부터 N까지의 순열인 N개의 점이 주어질 때, xi<xj이고 yi<yj이며 두 점이 이루는 직사각형 내부에 다른 점이 없는 쌍의 개수를 센다.
문제
The organizers of an upcoming art exhibition decide to exhibit da Vinci’s famous artwork Lady with an Ermine on the largest wall of the exhibition hall. There are already many thumbtacks on the wall, and the organizers want to choose one thumbtack to nail the bottom left corner of the frame and another thumbtack to nail the top right corner of the frame. Obviously, there should not be any thumbnails within the rectangle area of the frame. The organizers can make a frame of any size to fit in the two chosen thumbtacks. Before choosing the pairs of thumbtacks, the organizers want to find out the number of ways to choose a valid pair of thumbtacks. Since there are too many thumbtacks on the wall, they ask you to write a program to help them find out the answer.
More formally, given N thumbtacks with coordinates (xi, yi), the organizers want to find the number of pairs (i, j) such that xi < xj and yi < yj, while no other thumbtack lies in the rectangular area with (xi, yi) as the bottom left corner and (xj, yj) as the top right corner; In other words, there should not be any k such that xi < xk < xj and yi < yk < yj.
To make your computation easier, the oganizers have normalized the x, y coordinates of thumbtacks into integers between 1 ∼ N. Moreover, no two thumbtacks share the same x-coordinate, nor are there two thumbtacks sharing the same y-coordinate.
입력
The first line contains a number 1 ≤ K ≤ 10, which is the number of input data sets in the file. This is followed by K data sets of the following form:
The first line of the data set contains an integer 1 ≤ N ≤ 100000, the number of thumbtacks on the wall. This is followed by N lines, each containing two integers xi, yi separated by space, describing the position of the i-th thumbtack.
It is guaranteed that xi’s and yi’s are both a permutation of 1 ∼ N; In other words, 1 ≤ xi, yi ≤ N, all xi’s are distinct, and all yi’s are distinct.
출력
For each data set, first output “Data Set x:” on a line by itself, where x is its number. Then output the number of ways da Vinci can hang a painting on the wall.
Each data set should be followed by a blank line.