hdu 4562 守护雅典娜 (Simple Geometry + dp)

http://acm.hdu.edu.cn/showproblem.php?pid=4562

　　中文题。

　　这道题的做法是先筛选出那些能够起到分隔雅典娜和怪兽的圆，就是那些只包围雅典娜或者只包围怪兽的圆，这样就分离出两种圆。因为不能同时对这两种圆进行dp，所以我们可以分别dp出最优解之后再对两种圆的最优解进行合并。这种dp就像是LIS，我们需要先对圆的大小进行排序，保证的是大的圆围在小的圆外面，这样就可以避免判断当前圆是否跟那个圆集里任何一个圆相交。

代码如下：

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 #include <vector>
 7 
 8 using namespace std;
 9 
10 struct Circle {
11     int x, y, r;
12 } ;
13 
14 struct Point {
15     int x, y;
16 } mon, ath;
17 
18 template <class T> T sqr(T x) { return x * x;}
19 vector<Circle> vath, vmon;
20 
21 bool cmp(Circle a, Circle b) { return a.r < b.r;}
22 
23 bool check(Circle a, Circle b) {
24     int dis = sqr(a.x - b.x) + sqr(a.y - b.y);
25     int dr = sqr(a.r - b.r), sr = sqr(a.r + b.r);
26     return !(dr <= dis && dis <= sr);
27 }
28 
29 bool inCir(Point x, Circle a) {
30     int dis = sqr(x.x - a.x) + sqr(x.y - a.y), r2 = sqr(a.r);
31     return dis < r2;
32 }
33 
34 bool onCir(Point x, Circle a) {
35     int dis = sqr(x.x - a.x) + sqr(x.y - a.y), r2 = sqr(a.r);
36     return dis == r2;
37 }
38 
39 int dp1[1111], dp2[1111];
40 
41 int main() {
42 //    freopen("in", "r", stdin);
43     int T, n;
44     cin >> T;
45     Circle tmp;
46     for (int cas = 1; cas <= T; cas++) {
47         cin >> n >> mon.x >> mon.y;
48         ath.x = ath.y = 0;
49         vath.clear(), vmon.clear();
50         while (n--) {
51             cin >> tmp.x >> tmp.y >> tmp.r;
52             bool a = inCir(ath, tmp), b = inCir(mon, tmp);
53             if (!onCir(ath, tmp) && !onCir(mon, tmp) && (a ^ b)) { // 分离出有用的圆
54                 if (a) vath.push_back(tmp);
55                 else vmon.push_back(tmp);
56             }
57         }
58         int sz1 = vath.size(), sz2 = vmon.size();
59         sort(vath.begin(), vath.end(), cmp);
60         sort(vmon.begin(), vmon.end(), cmp);
61         int mx = 0;
62         for (int i = 0; i < sz1; i++) { // 对包围雅典娜的圆dp
63             dp1[i] = 0;
64             for (int j = 0; j < i; j++) {
65                 if (check(vath[i], vath[j])) dp1[i] = max(dp1[i], dp1[j]);
66             }
67             dp1[i]++;
68             mx = max(mx, dp1[i]);
69 //            cout << dp1[i] << ' ';
70         }
71 //        cout << endl;
72         for (int i = 0; i < sz2; i++) { // 对包围怪兽的圆dp
73             dp2[i] = 0;
74             for (int j = 0; j < i; j++) {
75                 if (check(vmon[i], vmon[j])) dp2[i] = max(dp2[i], dp2[j]);
76             }
77             dp2[i]++;
78             mx = max(mx, dp2[i]);
79 //            cout << dp2[i] << ' ';
80         }
81 //        cout << endl;
82         for (int i = 0; i < sz1; i++) { // 对两种dp值合并，从而得到所需的答案
83             for (int j = 0; j < sz2; j++) {
84                 if (check(vath[i], vmon[j])) {
85                     mx = max(mx, dp1[i] + dp2[j]);
86                 }
87             }
88         }
89         printf("Case %d: %d\n", cas, mx);
90     }
91     return 0;
92 }

View Code

——written by Lyon