POJ 1328 - Radar Installation

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

概要

半径 d の領域を照らせる灯台をいくつか x 軸上に置いて，n 個の島すべてを照らしたい． そのときに必要な最低限の灯台はいくつか答える．

ただし，すべての島を照らせないときは -1 を出力する．

制約

• 1 <= n <= 1000

解法

y 座標が d より大きい島があったときは -1．

そうでないときは，左からなるべく右側に貪欲に灯台を置いていくのが最適．

cin/cout を使ったら TLE だった… (テストケースが大量にある…？)

 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 namespace std {
10   bool operator<(const P& lhs, const P& rhs)
11   {
12     if (abs(lhs.real() - rhs.real()) < EPS) {
13       return lhs.imag() < rhs.imag();
14     } else {
15       return lhs.real() < rhs.real();
16     }
17   }
18 };
19 
20 inline double sqr(double x) { return x*x; }
21 
22 int main()
23 {
24   int Ti = 0;
25   int n, d;
26   while (scanf("%d %d", &n, &d) != EOF && n != 0) {
27     vector<pair<double, P> > ps(n);
28     bool ng = false;
29     for (int i = 0; i < n; i++) {
30       int x, y;
31       scanf("%d %d", &x, &y);
32       ps[i].second = P(x, y);
33       ng = ng || abs(ps[i].second.imag()) > d;
34       ps[i].first = ps[i].second.real() + sqrt(sqr(d) - sqr(ps[i].second.imag()));
35     }
36     int ans = 0;
37     if (ng) {
38       ans = -1;
39     } else {
40       sort(ps.begin(), ps.end());
41       for (vector<pair<double,P> >::const_iterator it = ps.begin(); it != ps.end();) {
42         ++ans;
43         const P p(it->first, 0.0);
44         while (it != ps.end() && abs(it->second - p) <= d + EPS) {
45           ++it;
46         }
47       }
48     }
49     printf("Case %d: %d\n", ++Ti, ans);
50   }
51   return 0;
52 }