Jisuanke - t2063_ Missile interception

 

 

//
 Answer key :

     take   The distance from the missile to the two systems (d1 d2)  Form a structure   For missiles to  1 The distance of system No (d1)  Sort from big to small 
     And then we're going to iterate   If and only if  a[i].d1 + ( 1~i-1  in  a[i].d2  The maximum of  )  At the very least   That's the answer. 
     Be careful   There is such a situation  1 The No. 1 system does not have to intercept any missiles 

     It is equivalent to dividing the missiles into two piles   Ask the sum of their respective maximum values   Just arrange the maximum value of one pile first 

//
#include<bits/stdc++.h>
using namespace std;

const int MAXN=1e5+6;

typedef struct missile
{
    int d1,d2;
}T;
T a[MAXN];

bool cmp( T a,T b )
{
    return a.d1>b.d1;   //  Value of expression 
}

int main()
{
    int x1,yl,x2,y2,n,i,x,y,maxd2,ans;      // yl

    while( ~scanf("%d%d%d%d%d",&x1,&yl,&x2,&y2,&n) )
    {
        memset( a,0,sizeof( a ) );

        for( i=0;i<n;i++ )
        {
            scanf("%d%d",&x,&y);
            a[i].d1=( x1-x )*( x1-x )+( yl-y )*( yl-y );    //  Negative is positive 
            a[i].d2=( x2-x )*( x2-x )+( y2-y )*( y2-y );
        }
        sort( a,a+n,cmp );

        ans=a[0].d1;                    //  initialization 
        maxd2=a[0].d2;
        for( i=1;i<=n;i++ )             // i<=n: 1 The system may not need to intercept missiles 
        {
            ans=min( ans,maxd2+a[i].d1 );
            maxd2=max( maxd2,a[i].d2 );
        }
        printf("%d\n",ans);
    }
    return 0;
}

//
find:
01  Calculation scale  1<=N<=1e5,abs<=1e3 --> d<=2*1e8 < int
02 cmp  direct  return  Value of expression 
03  Global variables  y1  name conflict   Just use  yl yi  wait  (  There is a header file defined  y1 )
04  Negative is positive 
05  Initialization should be in place (a[n]=0) 1 The system may not need to intercept missiles  
06  Clarify the logical relationship 

00  Why did you think wrong at first  

     There may be   front  1 System   The working radius is large  
     Then suddenly there is a distance  2 System   Near some very far missiles  
     Lead to direct  1 System   The working radius of includes 

00  Fast reading