CC

自然万物都趋向从有序变得无序

0%

Count Squares HDU 3432

发表于 更新于 分类于 Valine：

题目链接:

题目

Given a set of points with integer coordinates xi, yi, i = 1…N, your program must find all the squares having each of four vertices in one of these points.

Input

Input file contains integer N followed by N pairs of integers xi yi.
Constraints
-104 ≤ xi, yi ≤ 104, 1 ≤ N ≤ 2000. All points in the input are different.

Output

Output file must contain a single integer — number of squares found.

Sample Input

Sample input 1
4 0 0 4 3 -3 4 1 7
Sample input 2
9
1 1  1 2  1 3  
2 1  2 2  2 3  
3 1  3 2  3 3

Sample Output

Sample output 1
1
Sample output 2
6

Hint

Bold texts appearing in the sample sections are informative and do not form part of the actual data.

题意:

给你 n 个点,判断存在多少个正方形.

思路:

枚举两个点 || 正方形的边, 然后根据枚举的两个点算出未知的两个点,然后在给出的点中查找这两个点是否出现,如果出现则说明存在正方形,反之说明不存在.

查找的话可以使用hash 或者 map, 但是map 我没有试过,不知道具体能不能行.

代码:

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
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;

const int prime = 1999;

typedef class{
public:
    int x,y;
}node;

typedef class Hash{//手动写hash表
public:
    int x, y;
    Hash *next;
    Hash(){
        next = 0;
    }
}Hash;

node a[2000+10];
Hash *has[prime];

void insert_hash(int pos){
//hash的对应法则,我们采用平方和
    int k = (a[pos].x * a[pos].x + a[pos].y * a[pos].y) % prime + 1;
    if(!has[k]){
        Hash *tmp = new Hash;
        tmp->x = a[pos].x;
        tmp->y = a[pos].y;
        has[k] = tmp;
    }else {
        Hash * tmp = has[k];//如果这个点出现过
        while(tmp->next)
            tmp = tmp->next;
        tmp->next = new Hash;
        tmp->next->x = a[pos].x;
        tmp->next->y = a[pos].y;
    }
}

bool Find(int x, int y){
    int  k = (x * x + y * y) % prime + 1;
    if(!has[k]) return false;
    Hash * tmp = has[k];
    while(tmp){
        if(tmp->x == x && tmp->y == y)
            return true;
        tmp = tmp->next;
    }return false;
}

int main(){
    int n;
    while(scanf("%d", &n) != EOF && n){
        memset(has,0, sizeof(has));
        for(int  i = 1; i <= n; ++i){
            scanf("%d %d", &a[i].x, &a[i].y);
            insert_hash(i);
        }int num = 0;
        for(int i = 1; i <= n; ++i)
            for(int j = i+1; j <= n; ++j){
                int x = a[j].x - a[i].x;//根据已知点算正方形未知点的坐标
                int y = a[j].y - a[i].y;

                int x1 = y + a[i].x;
                int y1 = a[i].y - x;
                int x2 = y + a[j].x;
                int y2 = a[j].y - x;
                if(Find(x1,y1) && Find(x2,y2))
                    ++num;
                x1 = a[i].x - y;
                y1 = a[i].y + x;
                x2 = a[j].x - y;
                y2 = a[j].y + x;
                if (Find(x1,y1) && Find(x2,y2))
                    ++num;
            }printf("%d\n",num/4);//由于每个正方形被算了四次,所以除以4
    }return 0;
}