POJ 1328 - Radar Installation

#include<cstdio>

#include<cmath>

#include<algorithm>

#define f first

#define s second

using namespace std;

typedef pair<double,double> dd;

dd isl[10001],rad[10001];

int main(){

int N,d;

for(int T=1;~scanf("%d%d",&N,&d);T++){//EOF까지 받음

//if(N+d==0)break; 필요없음

for(int i=0;i<N;i++)

scanf("%lf%lf",&isl[i].f,&isl[i].s);

bool fail=0;

for(int i=0;i<N&&!fail;i++){

if(d>0&&d*d>=isl[i].s*isl[i].s){

//각각의 섬에 대해 레이더를 놓을 수 있는 경우를 저장함 :

//섬이 레이더 반경의 오른쪽 끝에 걸치게 하는 경우 레이더의 x좌표 : rad[i].f

//섬이 레이더 반경의 왼쪽 끝에 걸치게 하는 경우 레이더의 x좌표 : rad[i].s

double dist=sqrt(d*d-isl[i].s*isl[i].s);

rad[i].f=isl[i].f-dist;

rad[i].s=isl[i].f+dist;

}else fail=1;//레이더로 커버가 불가능함.

}

if(fail){

printf("-1\n");//불가능하면 -1

continue;

}

//레이더들을 rad[i].f 기준으로 정렬한다.

sort(rad,rad+N);

int ans=1;

double nr=rad[0].s;

for(int i=1;i<N;i++){

if(rad[i].f<=nr){

//현재 레이더로 다음 섬까지 커버 가능한 경우

if(nr>rad[i].s)nr=rad[i].s;

}

else{

//아닌 경우

ans++;

nr=rad[i].s;

}

}

printf("%d\n",ans);

}

return 0;

}