문제2335--North-Western Winds

2335: North-Western Winds

실행시간 제한: 5 Sec  메모리사용 제한: 128 MB
제출: 21  통과: 11
[제출] [채점기록] [묻고답하기]

문제 설명

A strong North-Western wind is blowing. When sailing this means that you can sail to the East, to the South or to any direction between East and South. It is impossible to go either North- or Westwards.

In the ocean there are a large number of small islands. These islands are described by coordinate pairs (x, y) on a grid. The positive y-direction is Northwards and the positive x-direction is Eastwards. We’d like to sail from one island to another. For how many pairs of islands is this possible? (Note: a pair consists of two different islands.)

입력 설명

The first line of the input file contains a single number: the number of test cases to follow. Each test case has the following format:

  • One line with one number n with 1 ≤ n ≤ 75,000: the number of islands.
  • n lines with two numbers xi and yi with −1,000,000,000 ≤ xi, yi ≤ 1,000,000,000: the coordinates of the islands. No two islands are located at the same coordinates.

출력 설명

For every test case in the input file, the output should contain a single number, on a single line: the number of pairs of islands for which you can sail from one to the other.

입력 예시 Copy

2
4
-10 -10
-10 10
10 -10
10 10
3
1 3
2 2
3 1

출력 예시 Copy

5
3

출처/분류

BAPC 2005