[NOIP 2010] 미사일 요격 T3 욕심

제목
11 년 간 의 도 광 양 회 를 거 쳐 모 국 연 은 새로운 미사일 요격 시스템 을 발 표 했 는데 그 와 의 거리 가 작업 반경 을 초과 하지 않 는 미사일 은 모두 성공 적 으로 차단 할 수 있다.작업 반경 이 0 이면 그 위치 와 똑 같은 미사일 을 차단 할 수 있다.그러나 이 미사일 요격 시스템 에 도 이런 결함 이 있다. 시스템 마다 하루 에 한 번 만 작업 반경 을 설정 할 수 있다.이날 사용 대 가 는 모든 시스템 작업 반경 의 제곱 이다.
어느 날 레이더 가 적국 의 미사일 습격 을 포착 했다.이 시스템 은 아직 시험 단계 에 있 기 때문에 두 개의 시스템 만 작업 에 투입 된다.지금 요구 가 모든 미사일 을 차단 하 는 것 이 라면 이날 의 최소 사용 대 가 를 계산 해 보 자.
첫 번 째 줄 은 4 개의 정수 x1, y1, x2, y2 를 포함 하고 두 개의 정수 사이 에 하나의 빈 칸 으로 나 누 어 이 두 미사일 요격 시스템 의 좌 표 는 각각 (x1, y1), (x2, y2) 임 을 나타 낸다.
두 번 째 줄 은 1 개의 정수 N 을 포함 하여 N 개의 미사일 이 있다 는 것 을 나타 낸다.다음 N 줄 은 줄 마다 두 개의 정수 x, y 이 고 중간 은 하나의 빈 칸 으로 나 누 어 미사일 의 좌표 (x, y) 를 나타 낸다.서로 다른 미사일 의 좌 표 는 같 을 수 있다.
생각:
             ....           。。。。                       
               a     
  a   i      a
     b
          
            ...     cmp
    A 

그래서 다음은 코드.
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
#define inf 0x3fffff
#define MAXN 100000+5
int n,x1,y1,x2,y2;
int mn=inf,rb;
inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}
struct data
{
    int x,y;
    int s1,s2;
};
data a[MAXN];
bool cmp(data a,data b)
{
    return a.s1<b.s1;
}
int main()
{
    cin>>x1>>y1>>x2>>y2>>n;
    for(int i=1;i<=n;++i)
    {
        a[i].x=read(),a[i].y=read();
        a[i].s1=(a[i].x-x1)*(a[i].x-x1)+(a[i].y-y1)*(a[i].y-y1);
        a[i].s2=(a[i].x-x2)*(a[i].x-x2)+(a[i].y-y2)*(a[i].y-y2);
    }
    sort(a+1,a+n+1,cmp);
    for(int i=n;i>0;--i)
        rb=max(a[i+1].s2,rb),mn=min(mn,a[i].s1+rb);
    cout<<mn;
}
        read()                 ...scanf   

그러면 이 간단 한 욕심 은 해 결 된 거 예요.

좋은 웹페이지 즐겨찾기