POJ 1266 - Cover an Arc.

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

概要

二次元座標上に弧の両端点と内点が与えられる． この弧を長方形のカーペットで覆いたい． そのときの長方形の面積を答える．

ただし，カーペットの縦および横の長さは整数値で，それぞれ軸に平行な向きで，カーペットの端の座標も整数値とする．

制約

解法

まず弧の中心 O を求めて，O を中心とした円の上下左右の座標を計算し，弧の上にあったらその座標，なかったら弧の端点の座標を採用する，というかんじにすれば，弧の最大・最小のx座標・y座標を求められる．

円周上のある点 P が弧の上に乗っているかどうかは，片方の端点を基準に，端点と内点の位置関係(外積)と，端点と P の位置関係が同じかどうかで判定する．

 1 #include <iostream>
 2 #include <complex>
 3 #include <cmath>
 4 using namespace std;
 5 typedef complex<double> P;
 6 
 7 inline double cross(const P& a, const P& b)
 8 {
 9   return a.real()*b.imag() - b.real()*a.imag();
10 }
11 
12 struct line
13 {
14   P a, b;
15   line(const P& x, const P& y) : a(x), b(y) {}
16 
17   inline P intersection(const line& ln) const
18   {
19     const P x = b - a;
20     const P y = ln.b - ln.a;
21     return a + x*(cross(y, ln.a - a))/cross(y, x);
22   }
23 };
24 
25 P circle_center(const P& a, const P& b, const P& c)
26 {
27   const P m = (a+b)/2.0;
28   const P n = (b+c)/2.0;
29   const P x = m + (b-a)*P(0,1);
30   const P y = n + (c-b)*P(0,1);
31   return line(m, x).intersection(line(n, y));
32 }
33 
34 inline bool arc_intersects(const P& a, const P& b, const P& c, const P& p)
35 {
36   return cross(b - a, c - a) * cross(b - a, p - a) > 0.0;
37 }
38 
39 int main()
40 {
41   P a, b, c;
42   cin >> a.real() >> a.imag() >> b.real() >> b.imag() >> c.real() >> c.imag();
43 
44   const P o = circle_center(a, b, c);
45   const double R = abs(a - o);
46   const P left = o + P(-R, 0);
47   const P right = o + P(R, 0);
48   const P bottom = o + P(0, -R);
49   const P top = o + P(0, R);
50 
51   const int x0 = floor(arc_intersects(a, b, c, left) ? left.real() : min(a.real(), b.real()));
52   const int x1 = ceil(arc_intersects(a, b, c, right) ? right.real() : max(a.real(), b.real()));
53   const int y0 = floor(arc_intersects(a, b, c, bottom) ? bottom.imag() : min(a.imag(), b.imag()));
54   const int y1 = ceil(arc_intersects(a, b, c, top) ? top.imag() : max(a.imag(), b.imag()));
55   cout << (x1 - x0)*(y1 - y0) << endl;
56   return 0;
57 }
poj/1266.cc