Next Spaceship

Driving into future…

POJ 2002 Squares

| Comments

Here is my pseudo code:

1
2
3
4
5
6
7
count <-- 0
for each edge( two points) do
    find the possible other two points to construct a square, there will be two pairs.
    for each pair of points do
        use binary search or hash to check if both points are given
        if both are given then count <-- count+1
return count

If you use binary search, you should quick sort the point set, the time complexity is \(O(n^2\log {n})\). If you use a good hash, the time complexity can be \(O(n^2)\).

Here is the source code:

POJ 2002 Squares
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
#include <iostream>
#include <algorithm>
#include <utility>
using namespace std;
#define N 1001
int n;
pair<int,int> p[N];
int d[N];
int main(){
    int i,j,r;
    while(cin>>n&&n){
        for(i=0;i<n;i++){
            scanf("%d%d",&p[i].first,&p[i].second);
        }
        sort(p,p+n);
        r=0;
        for(i=0;i<n-1;i++){
            for(j=i+1;j<n;j++){
                int x0=p[j].first-p[i].first,y0=p[j].second-p[i].second;
                int a=y0+p[i].first,b=-x0+p[i].second;
                int c=y0+p[j].first,d=-x0+p[j].second;
                if(binary_search(p,p+n,make_pair(a,b))&&binary_search(p,p+n,make_pair(c,d)))
                    r++;
                a=-y0+p[i].first,b=x0+p[i].second;
                c=-y0+p[j].first,d=x0+p[j].second;
                if(binary_search(p,p+n,make_pair(a,b))&&binary_search(p,p+n,make_pair(c,d)))
                    r++;
            }
        }
        printf("%d\n",r/4);
    }
    return 0;
}

Comments