Problema A - Pontos e Rectângulos

A Ana e o Aniceto são dois amigos que gostam muito de jogos e puzzles. Desta vez estão a discutir animadamente as melhores tácticas para um novo jogo sobre pontos e rectângulos.

Numa folha de papel está desenhada uma grelha e estão colocados nos vértices dessa grelha exactamente N pontos. Cada par de pontos forma um rectângulo onde os pontos correspondem a vértices desse mesmo rectângulo. A figura seguinte ilustra uma folha de papel com 6 pontos e dois possíveis rectângulos: um formado pelo par de pontos 1 e 2, e outro formado pelo par de pontos 4 e 6. Nota que mais rectângulos podiam ser formados escolhendo outros pares de pontos.

Em cada momento do jogo, um jogador pode escolher um par de pontos para retirar, desde que o rectângulo por eles formado não contenha nenhum outro ponto. No exemplo da figura, os pares (1,2) ou (1,3) seriam exemplos válidos para retirar, uma vez que os rectângulos por eles formados não contêm nenhum outro ponto. Já o rectângulo (4,6) não podia ser escolhido, porque contém o ponto 5. Outro exemplo de um par que não se pode retirar seria o rectângulo (2,5), porque contém os pontos 1 e 3.

A Ana e o Aniceto precisam da tua ajuda para jogar o jogo e para já estão interessados em saber, numa dada situação do jogo, quantos pares de pontos são possíveis de retirar. No exemplo da figura, existem exactamente 11 pares de pontos possíveis de retirar: (1,2), (1,3), (1,4), (1,5), (1,6), (2,3), (3,4), (3,5), (3,6), (4,5) e (5,6). Já os pares (2,4), (2,5), (2,6) e (4,6) não podem ser retirados. Tens de os ajudar!

O Problema

Dados um conjunto de N pontos com coordenadas inteiras (Xi, Yi), a tua tarefa é fazer um programa que diga quantos pares de pontos existem tal que o rectângulo por eles formado (como atrás descrito) não contém nenhum outro ponto. As coordenadas são todas diferentes e não existem duas coordenadas X ou Y repetidas.

Input

Na primeira linha do input vem um número inteiro N indicando o número de pontos a considerar. Seguem-se exactamente N linhas, cada uma contendo dois números inteiros separados por um espaço, indicando respectivamente as coordenadas Xi e Yi do i-ésimo ponto.

Os pontos podem vir por qualquer ordem e é garantido que não existem coordenadas X e Y repetidas, ou seja, para um qualquer i diferente de j, Xi é diferente de Xj e Yi é diferente de Yj.

Output

O output deve ser constituído por uma única linha contendo o número de pares de pontos que formam rectângulos que não contêm outros pontos.

Restrições

São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:

2 ≤ N ≤ 10 000       Número de pontos
1 ≤ Xi, Yi ≤ 2 000 000 000       Coordenadas dos pontos

Nota sobre a avaliação

Para um conjunto de casos de teste valendo 40% dos pontos, acontece sempre que N≤100, Xi≤1000 e Yi≤1000. Para um conjunto de casos de teste valendo 60% dos pontos, acontece sempre que Xi≤1000 e Yi≤1000.

Exemplo de Input

6
2 4
1 1
3 2
7 3
6 5
5 6

Exemplo de Output

11

Final Nacional das ONI'2011
Departamento de Ciência de Computadores
Faculdade de Ciências da Universidade do Porto
(27 de Maio de 2011)