题解 P1158 【导弹拦截】

· · 题解

首先，这道题一看，其实就是一道曼哈顿距离+排序+暴力的思想，首先曼哈顿距离就是求平面直角坐标系中两点的距离，我们首先求出每个点的距离，在由大到小排序（要用C++）哦！，我们在用一个minn来储存最小值，所以大致的思想就是这样，话不多说，上代码！ 

#include<bits/stdc++.h>
using namespace std;
int X1,Y1,X2,Y2,n=0,minn,r,x,y;
struct data {
    int r1,r2;
} a[12345667];//结构体，定义两个变量
bool cmp(data a,data b) {
    return a.r1>b.r1;
}//自行判断c++stl里的sort由大到小排列
int main() {
    cin>>X1>>Y1>>X2>>Y2>>n;
    for(int i=1; i<=n; i++) {
        cin>>x>>y;
        a[i].r1=(X1-x)*(X1-x)+(Y1-y)*(Y1-y);
        a[i].r2=(X2-x)*(X2-x)+(Y2-y)*(Y2-y);
    }//储存曼哈顿距离
    sort(a+1,a+n+1,cmp);//排序
    int i=2,rr1=a[1].r1,rr2=0;
    minn=rr1+rr2;//定义最小值
    while(i<=n) {
        rr2=max(rr2,a[i-1].r2);
        rr1=a[i].r1 ;
        minn=min(minn,rr1+rr2);
        i++;
    }//暴力思想
    cout<<minn;
    return 0;
}

好了就到此为止，是不是SO EASY！