POJ 1675 - Happy Birthday!

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

概要

原点を中心とする半径 r の円形のケーキの上に，3つのイチゴがそれぞれ (x1,y1), (x2,y2), (x3,y3) の位置にある．

これを各ピースに1つイチゴが乗っているように3等分できるかどうか答える．

制約

解法

各点同士のなす角を計算し，それの最大値が120度以上だった場合は No．

ただし，原点にイチゴがある場合がコーナーケースになっていて，イチゴを切ってはならないので No と答える．

原点とイチゴの距離が r より大きい場合も No と答えるように書いたけど，他の人の解答によるとこれをチェックしなくても通るらしい (r の意味が無い…)．

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <complex>
 4 #include <cmath>
 5 using namespace std;
 6 typedef complex<double> P;
 7 static const double PI = acos(-1.0);
 8 
 9 inline double dot(const P& a, const P& b)
10 {
11   return a.real()*b.real() + a.imag()*b.imag();
12 }
13 
14 bool solve(int r, const P& p1, const P& p2, const P& p3)
15 {
16   const double r1 = abs(p1);
17   const double r2 = abs(p2);
18   const double r3 = abs(p3);
19   if (r1 > r || r2 > r || r3 > r) {
20     return false;
21   }
22   const double ang[3] = {
23     acos(dot(p1, p2) / (r1 * r2)),
24     acos(dot(p2, p3) / (r2 * r3)),
25     acos(dot(p3, p1) / (r3 * r1)),
26   };
27   return *max_element(ang, ang+3) > 2*PI/3.0;
28 }
29 
30 int main()
31 {
32   int T;
33   cin >> T;
34   while (T-- > 0) {
35     int r, x1, y1, x2, y2, x3, y3;
36     cin >> r >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
37     if ((x1 == 0 && y1 == 0) || (x2 == 0 && y2 == 0) || (x3 == 0 && y3 == 0)) {
38       cout << "No" << endl;
39     } else {
40       cout << (solve(r, P(x1,y1), P(x2,y2), P(x3,y3)) ? "Yes" : "No") << endl;
41     }
42   }
43   return 0;
44 }
poj/1675.cc