[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
그러면 이 간단 한 욕심 은 해 결 된 거 예요.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.