#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;

}


그거 참 흥미로운 사실이네요.

'Random' 카테고리의 다른 글

GMail 전달 기능에 대한 불평  (0) 2015.11.03
새 블로그  (0) 2015.08.08
심해의 조각들  (0) 2015.03.03
옛날 생각  (0) 2014.07.27
  (0) 2013.06.23


C_Arrays.pptx


ㅋㅋ여름방학에 친구들 가르쳐주려고 만들었던 강의자료..

배열 기초에 대해 다뤘습니다.

'Computer' 카테고리의 다른 글

Select-Based nonblocking I/O processing  (0) 2012.11.04
Windows 콘솔 색상 변경, 커서 이동, 크기 조절  (1) 2012.11.04
리눅스 콘솔 색상 변경  (0) 2012.11.04
POJ 1328 - Radar Installation  (0) 2012.09.16
알고리즘 공부.  (0) 2012.07.28