POJ 1418 - Viva Confetti

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

概要

n 枚の円形の紙吹雪が散らばっている．

各紙吹雪の中心の座標と半径が与えられるので，上から見たときに何枚の紙吹雪が見えるかを答える．

入力は下のほうにある紙吹雪から順に与えられる．

制約

解法

まず，自分より上の円と共通部分を持たないような円は見えている．

それ以外の円については，ある直線 x = x1 上で少しでも見えていれば，その円は「見えている」と判断できる．

この x1 のとり方として，

を候補として調べ上げたら通った．若干怪しい…

  1 #include <cstdio>
  2 #include <vector>
  3 #include <complex>
  4 #include <algorithm>
  5 #include <cmath>
  6 using namespace std;
  7 typedef complex<double> P;
  8 static const double EPS = 1e-13;
  9 
 10 inline double dot(const P& p, const P& q) { return p.real()*q.real() + p.imag()*q.imag(); }
 11 inline double cross(const P& a, const P& b) { return a.real()*b.imag() - b.real()*a.imag(); }
 12 
 13 struct line
 14 {
 15   P a, b;
 16   line() {}
 17   line(const P& p, const P& q) : a(p), b(q) {}
 18 
 19   inline double distance(const P& p) const
 20   {
 21     return cross(b - a, p - a)/abs(b - a);
 22   }
 23 
 24   inline P perpendicular(const P& p) const
 25   {
 26     const double t = dot(p-a, a-b) / dot(b-a, b-a);
 27     return a + t*(a-b);
 28   }
 29 };
 30 
 31 struct circle
 32 {
 33   P o;
 34   double r;
 35   circle() {}
 36   circle(const P& p, double x) : o(p), r(x) {}
 37 
 38   bool intersects(const circle& c) const
 39   {
 40     const double l = abs(o - c.o);
 41     return fabs(r - c.r) <= l && l <= r + c.r;
 42   }
 43 
 44   bool contains(const circle& c) const
 45   {
 46     return abs(o - c.o)+c.r <= r;
 47   }
 48 
 49   bool intersects(const line& ln) const
 50   {
 51     return abs(ln.distance(o)) <= r;
 52   }
 53 
 54   pair<P,P> intersection(const circle& c) const
 55   {
 56     // assert(intersects(c))
 57     const double d = abs(o - c.o);
 58     const double cos_ = (d*d + r*r - c.r*c.r) / (2*d);
 59     const double sin_ = sqrt(r*r - cos_*cos_);
 60     const P e = (c.o - o) / d;
 61     return make_pair(o + e*P(cos_, sin_), o + e*P(cos_, -sin_));
 62   }
 63 
 64   pair<P,P> intersection(const line& ln) const
 65   {
 66     const P h = ln.perpendicular(o);
 67     const double d = abs(h - o);
 68     P ab = ln.b - ln.a;
 69     ab /= abs(ab);
 70     const double l = sqrt(r*r - d*d);
 71     return make_pair(h + l*ab, h - l*ab);
 72   }
 73 };
 74 
 75 int main()
 76 {
 77   int N;
 78   while (scanf("%d", &N) != EOF && N != 0) {
 79     vector<circle> cs;
 80     for (int i = 0; i < N; i++) {
 81       double x, y, r;
 82       scanf("%lf %lf %lf", &x, &y, &r);
 83       cs.push_back(circle(P(x, y), r));
 84     }
 85     vector<double> xs;
 86     vector<int> visible(N, true);
 87     for (int i = 0; i < N; i++) {
 88       xs.push_back(cs[i].o.real());
 89       xs.push_back(cs[i].o.real() - cs[i].r);
 90       xs.push_back(cs[i].o.real() + cs[i].r);
 91       for (int j = i+1; j < N; j++) {
 92         if (cs[i].intersects(cs[j])) {
 93           visible[i] = visible[j] = false;
 94           const pair<P,P> r = cs[i].intersection(cs[j]);
 95           xs.push_back(r.first.real());
 96           xs.push_back(r.second.real());
 97           xs.push_back((r.first.real() + r.second.real())/2.0);
 98         } else if (cs[j].contains(cs[i])) {
 99           visible[i] = false;
100         }
101       }
102     }
103 
104     for (vector<double>::const_iterator it = xs.begin(); it != xs.end(); ++it) {
105       const line ln(P(*it, 0), P(*it, 1));
106       vector<pair<pair<double, double>, int> > v;
107       for (int i = 0; i < N; i++) {
108         if (cs[i].intersects(ln)) {
109           const pair<P,P> r = cs[i].intersection(ln);
110           double y1 = r.first.imag(), y2 = r.second.imag();
111           if (y1 > y2) {
112             swap(y1, y2);
113           }
114           // y1 <= y2
115           if (y2 - y1 > EPS) {
116             v.push_back(make_pair(make_pair(y1, y2), i));
117           }
118         }
119       }
120       for (vector<pair<pair<double, double>, int> >::const_iterator jt = v.begin(); jt != v.end(); ++jt) {
121         if (visible[jt->second]) {
122           continue;
123         }
124         double y1 = jt->first.first;
125         double y2 = jt->first.second;
126         for (vector<pair<pair<double, double>, int> >::const_iterator kt = v.begin(); kt != v.end(); ++kt) {
127           const double yy1 = kt->first.first;
128           const double yy2 = kt->first.second;
129           if (jt->second < kt->second && yy1 < y2+EPS && y1 < yy2+EPS) {
130             if (y2 < yy2 + EPS) {
131               y2 = min(y2, yy1);
132             }
133             if (yy1 < y1 + EPS) {
134               y1 = max(y1, yy2);
135             }
136           }
137         }
138         if (y2 - y1 > EPS) {
139           visible[jt->second] = true;
140         }
141       }
142     }
143     printf("%ld\n", count(visible.begin(), visible.end(), true));
144   }
145   return 0;
146 }
poj/1418.cc