一道看似暴力枚举实则就是暴力枚举（加点贪心）的题

题目：

经过 1111年的韬光养晦，某国研发出了一种新的导弹拦截系统，凡是与它的距离不超过其工作半径的导弹都能够被它成功拦截。当工作半径为 00时，则能够拦截与它位置恰好相同的导弹。但该导弹拦截系统也存在这样的缺陷：每套系统每天只能设定一次工作半径。而当天的使用代价，就是所有系统工作半径的平方和。

某天，雷达捕捉到敌国的导弹来袭。由于该系统尚处于试验阶段，所以只有两套系统投入工作。如果现在的要求是拦截所有的导弹，请计算这一天的最小使用代价。

最大数据范围：

对于100%的数据，1≤N≤100000，且所有坐标分量的绝对值都不超过1000。

 

 

首先，看到题目与数据范围可知，可直接保存坐标差的平方和，（就是两点距离公式的平方），不会爆炸，而且只需保存与两个拦截系统的距离，无需保存坐标。

其次考虑算法问题，如果单纯考虑某点与该两点距离远近比较，也就是考虑这个导弹离谁近就用哪个的话，并不保证正确性

因为也许某个导弹离点2较近，但点1的拦截距离已经可以囊括该导弹，就无需更新点2拦截范围

不妨考虑以下思路，

按照对于第一套拦截系统的距离排序，以保证第一套系统拦截范围为第k个点距离时，能够拦截到前k个点，因为前k个点距离要更短

然后在枚举以上内容过程中处理该点到第二个拦截点的距离，取最大，否则无法拦截到所有点

代码：

#include
     
      using namespace std;int n;struct node{    int df,ds;    node(){        df=0;        ds=0;    }}nd[100005];struct al{    int x,y;}fi,sc;inline bool cmp(const node &a,const node &b){    return a.df
      
       =1){        maxn=max(maxn,nd[i+1].ds);        ans=min(nd[i].df+maxn,ans);        i--;    }printf("%d\n",ans);    return 0;}