POJ 1375 - Intervals

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

概要

二次元平面上にひとつの光源と N 個の円があり，X 軸に床がある． すべての円は光源より低く，床より高い位置にある．

円は光を通さず，反射もしないとする．

このとき，床の上で円によって光が遮られている区間をすべて答える．

制約

解法

光源から各円への接線を求め，それと床との交点を求めて区間を列挙した後， ソートして被っている区間をマージしながら答える．

 1 #include <cstdio>
 2 #include <vector>
 3 #include <algorithm>
 4 #include <complex>
 5 #include <cmath>
 6 using namespace std;
 7 typedef complex<double> P;
 8 static const double EPS = 1e-6;
 9 
10 inline double cross(const P& a, const P& b) { return a.real()*b.imag() - b.real()*a.imag(); }
11 
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 P intersection(const line& ln) const
19   {
20     const P x = b - a;
21     const P y = ln.b - ln.a;
22     return a + x*(cross(y, ln.a - a))/cross(y, x);
23   }
24 };
25 
26 struct circle
27 {
28   P o;
29   double r;
30   circle() {}
31   circle(const P& p, double x) : o(p), r(x) {}
32 
33   pair<P,P> tangent(const P& p) const
34   {
35     const double L = abs(o - p);
36     const double M = sqrt(L*L - r*r);
37     const double theta = asin(r / L);
38     const P v = (o - p) / L;
39     return make_pair(p + M*(v*polar(1.0, theta)), p + M*(v*polar(1.0, -theta)));
40   }
41 };
42 
43 int main()
44 {
45   int N;
46   while (scanf("%d", &N) != EOF && N != 0) {
47     int bx, by;
48     scanf("%d %d", &bx, &by);
49     const P o(bx, by);
50     const line base(P(0, 0), P(1, 0));
51     vector<pair<double,double> > intervals(N);
52     for (int i = 0; i < N; i++) {
53       int x, y, r;
54       scanf("%d %d %d", &x, &y, &r);
55       const pair<P,P> ps = circle(P(x, y), r).tangent(o);
56       intervals[i] = make_pair(
57           base.intersection(line(o, ps.first)).real(),
58           base.intersection(line(o, ps.second)).real());
59       if (intervals[i].first > intervals[i].second) {
60         swap(intervals[i].first, intervals[i].second);
61       }
62     }
63 
64     sort(intervals.begin(), intervals.end());
65     pair<double,double> r = intervals[0];
66     for (int i = 1; i < N; i++) {
67       if (r.second + EPS > intervals[i].first) {
68         r.second = max(r.second, intervals[i].second);
69       } else {
70         printf("%.2f %.2f\n", r.first, r.second);
71         r = intervals[i];
72       }
73     }
74     printf("%.2f %.2f\n\n", r.first, r.second);
75   }
76   return 0;
77 }
poj/1375.cc