AcWing 443. 導彈攔截 題目鏈接
經過?11?年的韜光養晦，某國研發出了一種新的導彈攔截系統，凡是與它的距離不超過其作業半徑的導彈都能夠被它成功攔截，
當作業半徑為?0?時，則能夠攔截與它位置恰好相同的導彈，
但該導彈攔截系統也存在這樣的缺陷：每套系統每天只能設定一次作業半徑，
而當天的使用代價，就是所有系統作業半徑的平方和，
某天，雷達捕捉到敵國的導彈來襲，
由于該系統尚處于試驗階段，所以只有兩套系統投入作業，
如果現在的要求是攔截所有的導彈，請計算這一天的最小使用代價，
輸入格式
第一行包含?4?個整數x1、y1、x2、y2，每兩個整數之間用一個空格隔開，表示這兩套導彈攔截系統的坐標分別為(x1,y1)、(x2,y2)，
第二行包含?1?個整數N，表示有N顆導彈，接下來N行，每行兩個整數x、y，中間用一個空格隔開，表示一顆導彈的坐標(x,y)，不同導彈的坐標可能相同，
輸出格式
只有一行，包含一個整數，即當天的最小使用代價，
資料范圍
1≤N≤105,所有坐標分量的絕對值都不超過?1000，
輸入樣例：
0 0 6 0
5
-4 -2
-2 3
4 0
6 -2
9 1
輸出樣例：
30
其實我心血來潮，想做一下NOIP的題，然后遇到了這個題
這道題，其實我剛開始想著是離d1近的就擴大d1的半徑，離d2近的就擴大d2的半徑，但是這種思路很明顯不是很對，達不到區域最優解全域最優，然后我就想到了用排序來列舉更新r1,r2的思路，
首先排序把d1從小到大排好，然后再求出i+1-n的點距離x2,y2的最大值作為r2,dis1[i]為r1半徑，這樣就可以求出理想值了，思路可能說的不是很明白，代碼如下，
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=1e5+10;
typedef pair<int,int> PII;
#define d1 first
#define d2 second
PII dist[N];
int d[N];
int main(void)
{
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int a,b;
cin>>a>>b;
int t1,t2;
t1=(a-x1)*(a-x1)+(b-y1)*(b-y1);//距離x1,y1的距離
t2=(a-x2)*(a-x2)+(b-y2)*(b-y2);
dist[i]={t1,t2};
}
sort(dist+1,dist+1+n);
int res=-1010*1010;
for(int i=n;i>=1;i--)
{
res=max(res,abs(dist[i].d2));//求i-n的最大值
d[i]=res;
}
int cnt=0x3f3f3f3f;
for(int i=0;i<=n;i++)
{
cnt=min(cnt,dist[i].d1+d[i+1]);//注意這是i+1
}
cout<<cnt;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/262478.html
標籤：其他
上一篇：Win鍵失效解決方案+鍵盤檢測器
下一篇：25 萬行逆向原始碼遭下架！