POJ 2504 - Bounding box

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

概要

ある正 n 角形の異なる3つの頂点の座標が与えられるので，その正 n 角形の全ての頂点を覆う，辺々が x 軸 あるいは y 軸に平行な最小の長方形の面積を答える．

制約

解法

正 n 角形なので，3点の座標からその図形の形が一意に定まる．

3点を通る円の中心(外心)を求めて，1つの頂点から 2π/n ずつ回転させていくことですべての頂点の座標を計算できるので，それらの x, y それぞれの最大・最小を求めればよい．

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <vector>
 4 #include <complex>
 5 using namespace std;
 6 typedef complex<double> P;
 7 static const double EPS = 1e-6;
 8 static const double PI = acos(-1.0);
 9 
10 inline double dot(const P& a, const P& b) { return a.real()*b.real() + a.imag()*b.imag(); }
11 inline double cross(const P& a, const P& b) { return a.real()*b.imag() - b.real()*a.imag(); }
12 struct line/*{{{*/
13 {
14   P a, b;
15   line() {}
16   line(const P& p, const P& q) : a(p), b(q) {}
17 
18   inline bool parallel(const line& ln) const
19   {
20     return abs(cross(ln.b - ln.a, b - a)) < EPS;
21   }
22 
23   inline bool intersects(const line& ln) const
24   {
25     return !parallel(ln);
26   }
27 
28   inline P intersection(const line& ln) const
29   {
30     // assert(intersects(ln))
31     const P x = b - a;
32     const P y = ln.b - ln.a;
33     return a + x*(cross(y, ln.a - a))/cross(y, x);
34   }
35 
36   inline double distance(const P& p) const
37   {
38     return abs(cross(p - a, b - a)) / abs(b - a);
39   }
40 
41   inline P perpendicular(const P& p) const
42   {
43     const double t = dot(p-a, a-b) / dot(b-a, b-a);
44     return a + t*(a-b);
45   }
46 };/*}}}*/
47 
48 int main()
49 {
50   int N;
51   for (int Ti = 1; scanf("%d", &N) != EOF && N != 0; Ti++) {
52     P ps[3];
53     for (int i = 0; i < 3; i++) {
54       double x, y;
55       scanf("%lf %lf", &x, &y);
56       ps[i] = P(x, y);
57     }
58     const P a = (ps[0] + ps[1])/2.0;
59     const P aa = (ps[0] - a) * P(0, 1);
60     const line aaa(a, a+aa);
61     const P c = (ps[2] + ps[1])/2.0;
62     const P cc = (ps[2] - c) * P(0, 1);
63     const line ccc(c, c+cc);
64     const P o = aaa.intersection(ccc);
65     const double R = abs(ps[0] - o);
66 
67     double t = ps[0].imag(), b = ps[0].imag(), l = ps[0].real(), r = ps[0].real();
68     double theta = arg(ps[0] - o);
69     const double step = 2*PI/N;
70     for (int i = 0; i < N; i++) {
71       theta += step;
72       const P p = polar(R, theta) + o;
73       t = max(t, p.imag());
74       b = min(b, p.imag());
75       l = min(l, p.real());
76       r = max(r, p.real());
77     }
78     printf("Polygon %d: %.3f\n", Ti, (t-b)*(r-l));
79   }
80   return 0;
81 }
poj/2504.cc