[NOIP 2009][vijos 1810]ミサイル迎撃(列挙)
タイトルの説明
トランスファゲート
問題解
まずすべてのミサイルを最初の迎撃システムとの距離で並べ替え、最初のシステムが最も遠くどのミサイルを迎撃するかを列挙し、残りのミサイルは2番目のシステムによって迎撃される.答えを更新すればいいです.
コード#コード#
トランスファゲート
問題解
まずすべてのミサイルを最初の迎撃システムとの距離で並べ替え、最初のシステムが最も遠くどのミサイルを迎撃するかを列挙し、残りのミサイルは2番目のシステムによって迎撃される.答えを更新すればいいです.
コード#コード#
#include
#include
#include
#include
using namespace std;
#define N 100005
#define inf 2100000000
int n,a,b,c,d,Max,ans;
struct hp{int x,y,dis;}e[N];
int calc(int a,int b,int c,int d)
{
return (a-c)*(a-c)+(b-d)*(b-d);
}
int cmp(hp a,hp b)
{
return a.dis>b.dis;
}
int main()
{
scanf("%d%d%d%d",&a,&b,&c,&d);
scanf("%d",&n);
for (int i=1;i<=n;++i)
{
scanf("%d%d",&e[i].x,&e[i].y);
e[i].dis=calc(a,b,e[i].x,e[i].y);
}
sort(e+1,e+n+1,cmp);ans=inf;
for (int i=1;i<=n;++i)
{
ans=min(ans,e[i].dis+Max);
Max=max(Max,calc(c,d,e[i].x,e[i].y));
}
ans=min(ans,Max);
printf("%d
",ans);
}