#1497 : Queen Attack（類似八皇後經典問題的判斷）

描述

There are N queens in an infinite chessboard. We say two queens may attack each other if they are in the same vertical line, horizontal line or diagonal line even if there are other queens sitting between them.

Now given the positions of the queens, find out how many pairs may attack each other?

輸入

The first line contains an integer N.

Then N lines follow. Each line contains 2 integers Ri and Ci

No two queens share the same position.  

For 80% of the data, 1 <= N <= 1000

For 100% of the data, 1 <= N <= 100000, 0 <= Ri, Ci

輸出

One integer, the number of pairs may attack each other.

樣例輸入

5  
1 1  
2 2  
3 3   
1 3
3 1      

樣例輸出

10

前次一個網絡賽，遇到了一個n皇後問題，怕TLE，沒敢寫，後來發現，自己的想法是正确的，這裡又遇到了一個類似的問題，稍簡單些，用那個思路直接周遊一遍暴力，中間用四個數組判斷八個方向的情況（類似八皇後的判斷法），原來主要怕排序的時候炸，因為原來的資料量很大。

但是這裡還是因為數組太大炸了，因為資料量還可以，但是資料的大小太大了，本來可以離散化，但是這種二維的題，還有很多限制條件，牽一發而動全身，後來用map來代替四個數組判斷方向，這樣就能滿足離散化的要求，既不用離散化，數組的空間也不大。

#include <bits/stdc++.h>

using namespace std;
const int MA=110000;
struct poin
{
    int x,y;
}G[MA];
int cmp(poin a,poin b)
{
    if(a.y<b.y)return 1;
    else if(a.y==b.y)
    {
        if(a.x<b.x)return 1;
    }
    return 0;
}
map<int,int>X;
map<int,int>Y;
map<int,int>SH;
map<int,int>NI;

int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        scanf("%d%d",&G[i].x,&G[i].y);
    }
    sort(G,G+n,cmp);
    int sum=0;
    for(int i=0;i<n;i++)
    {
        int u=G[i].x,v=G[i].y;
        if(X[u])sum+=X[u];
        if(Y[v])sum+=Y[v];
        if(NI[u+v])sum+=NI[u+v];
        if(SH[u-v+n])sum+=SH[u-v+n];
        X[u]++;
        Y[v]++;
        NI[u+v]++;
        SH[u-v+n]++;
    }
    printf("%d\n",sum);

    return 0;
}