暑假作业竟然如此芳香（hdu4145枚举+贪心）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4145

题目：在一个坐标系上，有许多敌人，现在有两个火力范围是圆形的炮塔，如何才能在火力能覆盖所有人的情况下还能使两炮塔半径R1,R2的平方和R1^2+R2^2最小？

思路：一开始没搞明白，直接简单粗暴的想算出每个敌人到两炮台的距离，用这么一个转移方程来算

大意就是dp(i)表示第i个敌人所产生的最小费用,后来发现这道题每次决策都会相互影响，不能用这种动规的思想去写，百度了下还是直接贪心+枚举，只需要算出每个敌人到两个炮台的距离，其中一个炮台从大到小枚举，另外一个炮台从前一个炮台火力不能达到的范围枚举，维护一个最小值就可以了。

代码如下

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 100010;
 4 struct point {
 5     int x;int y;int da;int db;
 6 } c[maxn];
 7 bool cmp(point a,point b){
 8     return a.da<b.da;
 9 }
10 int main() {
11     int t;
12     scanf("%d",&t);
13     while(t--) {
14         int x1,y1,x2,y2;
15         scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
16         int n;
17         scanf("%d",&n);
18         for(int i=0;i<n;++i){
19             scanf("%d%d",&c[i].x,&c[i].y);
20             int x=c[i].x,y=c[i].y;
21             c[i].da=(x-x1)*(x-x1)+(y-y1)*(y-y1);
22             c[i].db=(x-x2)*(x-x2)+(y-y2)*(y-y2);
23         }
24         sort(c,c+n,cmp);
25         int min_d = c[n-1].da;
26         int tmp=0;
27         for(int i=n-2;i>=0;--i){
28             tmp=max(tmp,c[i+1].db);
29             min_d=min(min_d,tmp+c[i].da);
30         }
31         tmp=max(tmp,c[0].db);
32         min_d=min(min_d,tmp);
33         printf("%d
",min_d);
34     }
35     return 0;
36 }