首页 > ACM题库 > HDU-杭电 > hdu 2428 Stars-分治-[解题报告]C++
2014
01-26

hdu 2428 Stars-分治-[解题报告]C++

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;
}


解题转自:http://lcc3536.blog.163.com/blog/static/1324699172011820254241/


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

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。