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?
1174: Links时间限制: 1 Sec 内存限制: 128 MB
提交: 16 解决: 4
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