codevs 1128 导弹拦截 (贪心)

/*
题目大体意思是两套系统好多导弹
怎样分配使得两个系统所拦截的最大半径之和最小
贪心:把距离1系统最远的 让2拦截
记好距离 然后按照距离1由远到近排序
对于每一个导弹 如果这之前的都给2拦截 则1的半径就是ri
2的半径则是前面所有的的max ans就是两者之和
我们O(n)的跑一边 边跑边维护min就好了
*/
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define maxn 100010
using namespace std;
int n,s;
struct node
{
int ss1;
int ss2;
};
node aa[maxn];
int x11,y11,x22,y22;
int jisuan(int x1,int y1,int x2,int y2)
{
return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}
int cmp(const node &x,const node &y)
{
if(x.ss1>y.ss1)return ;
return ;
}
int main()
{
int i;
int a,b;
cin>>x11>>y11>>x22>>y22>>n;
for(i=;i<=n;i++)
{
cin>>a>>b;
int s1=jisuan(a,b,x11,y11);
int s2=jisuan(a,b,x22,y22);
aa[i].ss1=s1;
aa[i].ss2=s2;
}
sort(aa+,aa++n,cmp);
int tot=,mm=;
for(i=;i<=n;i++)
{
tot=min(tot,aa[i].ss1+mm);
mm=max(mm,aa[i].ss2);
}
cout<<tot;
}
上一篇:微信录音文件上传到服务器以及amr转化成MP3格式,linux上转换简单方法


下一篇:【接口时序】1、软件与Verilog基本格式规范说明