POJ 2002 - Squares

http://poj.org/problem?id=2002

概要

二次元座標上の \(n\) 個の格子点が与えられる。 この中に正方形が何個あるか答える。

制約

解法

2点選べば残りの2点の位置が決まるので、その2点が与えられた格子点に含まれているかどうかで数えればいい。 \(n ^ 2 \log n\) でちょっと厳しそうだけど、Time Limit が長めなのでこれでいい。 重複に注意。

 1 #include <cstdio>
 2 #include <vector>
 3 #include <set>
 4 #include <cmath>
 5 #include <complex>
 6 #include <algorithm>
 7 using namespace std;
 8 typedef complex<double> P;
 9 static const double EPS = 1e-6;
10 
11 namespace std {
12   bool operator<(const P& a, const P& b)
13   {
14     if (fabs(a.real() - b.real()) < EPS) {
15       return a.imag() < b.imag();
16     } else {
17       return a.real() < b.real();
18     }
19   }
20 };
21 
22 bool lattice(const P& p, pair<int,int>& pp)
23 {
24   pp.first = lround(p.real());
25   pp.second = lround(p.imag());
26   return fabs(pp.first - p.real()) < EPS && fabs(pp.second - p.imag() < EPS);
27 }
28 
29 int main()
30 {
31   int N;
32   while (scanf("%d", &N) != EOF && N != 0) {
33     vector<P> v;
34     set<pair<int,int> > s;
35     for (int i = 0; i < N; i++) {
36       int x, y;
37       scanf("%d %d", &x, &y);
38       v.push_back(P(x, y));
39       s.insert(make_pair(x, y));
40     }
41     sort(v.begin(), v.end());
42 
43     int ans = 0;
44     for (int i = 0; i < N; i++) {
45       for (int j = i+1; j < N; j++) {
46         const P d = (v[j] - v[i]) * P(0, 1);
47         if (d.real() < 0 || d.imag() < 0) {
48           continue;
49         }
50         const P p = v[i] + d;
51         const P q = v[j] + d;
52         pair<int,int> pp, qq;
53         if (lattice(p, pp) && lattice(q, qq)
54             && s.count(pp) && s.count(qq)) {
55           ++ans;
56         }
57       }
58     }
59     printf("%d\n", ans);
60   }
61   return 0;
62 }
poj/2002.cc