主页 讨论版 问题 名次 状态 统计
12月将举办首届西电ACM新生赛,敬请期待~~~~
问题 D: Links

问题 D: Links

时间限制: 1 Sec  内存限制: 128 MB
提交: 14  解决: 3
[提交][状态][讨论版]

题目描述

gcx is playing a game in which you need to link two of the towers to gain experience. Since each link of two towers will get the same experience, and each tower can establish link with any amount of towers. gcx wants to link all the towers which can be connect. She puts all the towers on a coordinate system, for any two towers, if there is a rectangle which is parallel to the axis of the coordinate system and this rectangle is containing only these two towers, gcx can connect them. (Containing means located inside the rectangle or on the edge) There are n towers on the coordinate system, gcx want to know how much pair of tower she can link at most. Can you help her to solve this problem?

输入

The first line of the input contains a single integer n (1 ≤ n ≤ 100000), the number of towers in the coordinate system. followed by n lines, the i-th line (1 ≤ i ≤ n) contains two integers xi and yi (|xi|,|yi| ≤ 1e9), separated by a space, (x, y) is the location of the i-th tower.

输出

One line contains a single integer, the number of pair of towers gcx can link at most.

样例输入

4
1 1
1 -1
-1 1
-1 -1

样例输出

4

提示

[提交][状态][讨论版]