2014
01-26

# Stars

Lucy loves stars very much. There are N (1 <= N <= 1000) stars in the sky. Assume the sky is a flat plane. All of the stars lie on it with a location (x, y), -10000 <= x, y <= 10000. Now, Lucy wants you to tell her how many squares with each of four vertices formed by these stars, and the edges of the squares should parallel to the coordinate axes.

The first line of input is the number of test case.
The first line of each test case contains an integer N. The following N lines each contains two integers x, y, meaning the coordinates of the stars. All the coordinates are different.

The first line of input is the number of test case.
The first line of each test case contains an integer N. The following N lines each contains two integers x, y, meaning the coordinates of the stars. All the coordinates are different.

2
1
1 2
4
0 0
1 0
1 1
0 1

0
1

# Stars

Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)

http://acm.hdu.edu.cn/showproblem.php?pid=2428

Problem Description
Lucy loves stars very much. There are N (1 <= N <= 1000) stars in the sky. Assume the sky is a flat plane. All of the stars lie on it with a location (x, y), -10000 <= x, y <= 10000. Now, Lucy wants you to tell her how many squares with each of four vertices formed by these stars, and the edges of the squares should parallel to the coordinate axes.

Input
The first line of input is the number of test case.
The first line of each test case contains an integer N. The following N lines each contains two integers x, y, meaning the coordinates of the stars. All the coordinates are different.

Output
For each test case, output the number of squares in a single line.

Sample Input
2  1  1 2  4  0 0  1 0  1 1  0 1

Sample Output
0  1

Source

Recommend
lcy

查找点有两种做法：1、对排好序的点进行二分查找，复杂度为 log(n)。
2、构建 hash 表，查找复杂度降为 O(1)。
搜索方法为：先搜索对角坐标是否存在，若存在，则搜索另外两个点，若都存在则计数器加一。

#include<stdio.h>
#include<stdlib.h>

struct
node{
int
x,y;
}
p[1001];

int
n;

int
cmp(const void * a, const void * b){
struct
node * aa = (struct node *) a;
struct
node * bb = (struct node *) b;

if
(aa->x != bb->x) return aa->x - bb->x;
else return
aa->y - bb->y;
}

bool
find(int a, int b){
int
l = 0;
int
r = n - 1;
while
(l <= r){
int
m = (l + r) / 2;
if
(p[m].x == a && p[m].y == b){
return
true;
}

else if
(a > p[m].x)
l = m + 1;
else if
(a < p[m].x)
r = m - 1;
else if
(b > p[m].y)
l = m + 1;
else

r = m - 1;
}

return
false;
}

int
main(void){
int
t;
scanf(“%d”,&t);
while
(t–){
scanf(“%d”,&n);
for
(int i=0;i<n;++i){
scanf(“%d%d”,&p[i].x,&p[i].y);
}

qsort(p,n,sizeof(p[0]),cmp);

int
max = 0;

for
(int i = 0; i < n; ++i){
int
a = p[i].x;
int
b = p[i].y;

for
(int j = i + 1; j<n; ++j){
if
(p[j].x - a == p[j].y - b){
if
(find(a , p[j].y) && find(p[j].x , b))
max++;
}
}
}

printf(“%d\n”,max);
}

return
0;
}

1. 思路二可以用一个长度为k的队列来实现，入队后判断下队尾元素的next指针是否为空，若为空，则出队指针即为所求。