Problem : 368 - 3B. 矩型計數

Problem Statistics

Solved Member: 6　　Submission: 23　　User Tried: 7

Statement:

給你平面上 n 個點 (X₁, Y₁)，(X₂, Y₂), ..., (X_n, Y_n)。問你有多少個數對 (i,j) 滿足：

1. 1 ≤ i,j ≤ n
2. X_i < X_j 且 Y_i < Y_j
3. (X_i, Y_i), (X_j, Y_j) 所圍成的矩型內部(不包含邊上)不包含其他點。(矩型四邊分別與 x 軸平行或垂直)

(感性題敘：選一個點當右上角，另一個點當左下角，且中間矩型為空的有幾個)

Input:Output:

第一行有一個整數 n ，代表點的個數。
接下來 n 行，每一行有兩個用空格分開的整數 X_i, Y_i，代表第 i 個點的位置。

限制：
1 ≤ n ≤ 200000
0 ≤ X_i,Y_i ≤ 1000000000
任兩個點 x 座標相異，且 y 座標相異

Subtask 1： n ≤ 400 (5分)
Subtask 2： n ≤ 5000 (10分)

輸出一個數字，代表滿足題目敘述條件的 (i,j) 有幾個。

Sample Input:Sample Output:

SAMPLE A:
4
0 0
2 2
3 4
4 3

SAMPLE B:
10
2 1
3 0
6 3
10 2
16 4
0 8
8 12
11 14
14 11
18 10

SAMPLE A:
3

SAMPLE B:
15

HINT:

SAMPLE A：
答案有三個
(0,0) (2,2) 形成的矩型
(2,2) (3,4) 形成的矩型
(2,2) (4,3) 形成的矩型

SAMPLE B圖示:

Source:

2013/2014 JOI 合宿 3模（日本IOI國手考）

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0-1	500ms	524288kb
0-2	500ms	524288kb
1-1	500ms	524288kb	5
1-2	500ms	524288kb
1-3	500ms	524288kb
1-4	500ms	524288kb
1-5	500ms	524288kb
1-6	500ms	524288kb
1-7	500ms	524288kb
1-8	500ms	524288kb
1-9	500ms	524288kb
1-10	500ms	524288kb
2-1	4000ms	524288kb	10
2-2	4000ms	524288kb
2-3	4000ms	524288kb
2-4	4000ms	524288kb
2-5	4000ms	524288kb
2-6	4000ms	524288kb
2-7	4000ms	524288kb
2-8	4000ms	524288kb
2-9	4000ms	524288kb
2-10	4000ms	524288kb
2-11	4000ms	524288kb
2-12	4000ms	524288kb
3-1	4000ms	524288kb	85
3-2	4000ms	524288kb
3-3	4000ms	524288kb
3-4	4000ms	524288kb
3-5	4000ms	524288kb
3-6	4000ms	524288kb
3-7	4000ms	524288kb
3-8	4000ms	524288kb
3-9	4000ms	524288kb
3-10	4000ms	524288kb
3-11	4000ms	524288kb
3-12	4000ms	524288kb
3-13	4000ms	524288kb
3-14	4000ms	524288kb
3-15	4000ms	524288kb
3-16	4000ms	524288kb
3-17	4000ms	524288kb
3-18	4000ms	524288kb
3-19	4000ms	524288kb
3-20	4000ms	524288kb