【HDOJ】2428 Stars

先排序后二分。
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 #define MAXN 1005
 8 
 9 typedef struct {
10     int x, y;
11 } node_st;
12 
13 node_st nodes[MAXN];
14 int n;
15 
16 bool comp(node_st a, node_st b) {
17     if (a.x == b.x)
18         return a.y < b.y;
19     else
20         return a.x < b.x;
21 }
22 
23 bool find(int x, int y) {
24     int l=0, r=n-1, mid;
25 
26     while (l <= r) {
27         mid = (l+r)>>1;
28         if (nodes[mid].x==x && nodes[mid].y==y)
29             return true;
30         if (nodes[mid].x > x)
31             r = mid - 1;
32         else if (nodes[mid].x < x)
33             l = mid + 1;
34         else if (nodes[mid].y > y)
35             r = mid - 1;
36         else
37             l = mid + 1;
38     }
39     return false;
40 }
41 
42 int main() {
43     int t, ans;
44     int i, j;
45 
46     scanf("%d", &t);
47     while (t--) {
48         scanf("%d", &n);
49         for (i=0; i<n; ++i)
50             scanf("%d%d", &nodes[i].x, &nodes[i].y);
51         sort(nodes, nodes+n, comp);
52         for (ans=0,i=0; i<n; ++i) {
53             for (j=i+1; j<n; ++j) {
54                 if ((nodes[i].x-nodes[j].x)==(nodes[i].y-nodes[j].y) && find(nodes[i].x, nodes[j].y) && find(nodes[j].x, nodes[i].y))
55                     ++ans;
56             }
57         }
58         printf("%d
", ans);
59     }
60 
61     return 0;
62 }