p1158题解

outstanding_c · 2018-09-09 20:00:09 · 题解

这道题是NOIP的第三题 只要你这道题做出来 一等奖就差不多了。 首先先用排序排出离第一发射台的距离，再枚举。 自然就出来了。

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
struct ab
{
    int x,y,j1,j2;//X，Y为坐标，J1为到一号导弹发射台的距离，J2为到二号导弹发射台的距离。
}a[100005];
bool cmp(ab a,ab b)//简单的结构体CMP
{
    return a.j1<b.j1;
}
int main()
{
    int x1,x2,y1,y2,j1,j2,minab=0,n,x,y,maxb=0;
    scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d%d",&a[i].x,&a[i].y);
    }
    for(int i=0;i<n;i++)//计算距离
    {
        a[i].j1=(a[i].x-x1)*(a[i].x-x1)+(a[i].y-y1)*(a[i].y-y1);
        a[i].j2=(a[i].x-x2)*(a[i].x-x2)+(a[i].y-y2)*(a[i].y-y2);
    }
    sort(a,a+n,cmp);//简单排序
    minab=a[n-1].j1;
    for(int i=1;i<n;i++)
    {
        x=a[n-i-1].j1;
        y=a[n-i].j2;
        if(y>maxb)maxb=y;//比较一下二号发射台谁的导弹半径大
        if((x+maxb)<minab)minab=x+maxb;
    }
    printf("%d",minab);//输出相加
}