时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述
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 indicating there is a queen in the Ri-th row and Ci-th column.
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 <= 1000000000

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

样例输入
5
1 1
2 2
3 3
1 3
3 1

样例输出
10

解题笔记

首先非常作死地使用了暴力法，毫不意外的，TLE…

C++ 实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<iostream>
#include<cmath>
#include<vector>
#include<cstring>

using namespace std;

bool judge(int x1,int y1,int x2,int y2){
    if(x1==x2){
        return true;
    }else if(y1==y2){
        return true;
    }else if(abs(y1-y2) == abs(x1-x2)){
        return true;
    }
    return false;
}

int main(){
    int data[100000+1][2];
    int n ;
    while (cin>>n) {
        memset(data, 0, sizeof(data));
        for (int i = 0; i < n; i ++) {
            cin >> data[i][0] >>data[i][1 ];
        }
        long count = 0;
        for (int i = 0; i < n; i ++) {
            for (int  j = i+1;  j < n; j ++) {
                if(judge(data[i][0],data[i][1],data[j][0],data[j][1])){
                    count ++;
                }
            }
        }
        cout<<count<<endl;
    }
    return 0;
}

随后考虑排序做法，根据x轴排序，根据y轴排序，根据k=1的斜线排序以及k=-1的斜线排序
分别统计结果

C++ 实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<cstring>

using namespace std;

struct xy_pair{
    long x;
    long y;
    long b1;
    long b2;
};

bool cmpx ( struct xy_pair a, struct xy_pair b ){
    return a.x < b.x;
}

bool cmpy ( struct xy_pair a, struct xy_pair b ){
    return a.y < b.y;
}

bool cmpb1 ( struct xy_pair a, struct xy_pair b ){
    return a.b1 < b.b1;
}

bool cmpb2 ( struct xy_pair a, struct xy_pair b ){
    return a.b2 < b.b2;
}
int main(){
    int n ;
    while (cin>>n) {
        struct xy_pair data[100000 + 1];
        memset(data, 0, sizeof(data));
        for (int i = 0; i < n;  i ++ ) {
            cin >> data[i].x >> data[i].y;
            data[i].b1 =  data[i].y - data[i].x ;
            data[i].b2 =  data[i].y + data[i].x ;
        }
        long sum = 0 ;
        long count = 1;
        sort(data, data+n, cmpx);
        for (int i = 1; i < n; i ++) {
            if (data[i].x == data[i-1].x) {
                count ++;
            }else{
                sum += count * (count-1) / 2;
                count = 1;
            }
        }
        sum += count * (count-1) / 2;
        sort(data, data+n, cmpy);
        count = 1;
        for (int i = 1; i < n; i ++) {
            if (data[i].y == data[i-1].y) {
                count ++;
            }else{
                sum += count * (count-1) / 2;
                count = 1;
            }
        }
        sum += count * (count-1) / 2;
        sort(data, data+n, cmpb1);
        count = 1;
        for (int i = 1; i < n; i ++) {
            if (data[i].b1 == data[i-1].b1) {
                count ++;
            }else{
                sum += count * (count-1) / 2;
                count = 1;
            }
        }
        sum += count * (count-1) / 2;
        sort(data, data+n, cmpb2);
        count = 1;
        for (int i = 1; i < n; i ++) {
            if (data[i].b2 == data[i-1].b2) {
                count ++;
            }else{
                sum += count * (count-1) / 2;
                count = 1;
            }
        }
        sum += count * (count-1) / 2;
        cout << sum << endl;
    }
    return 0;
}