poj1328

알고리즘: 정렬 + 욕심
제목: 해안 과 바다 가 있 습 니 다. 해안 은 곧 고 바 다 는 수평 입 니 다. 바다 에는 주어진 수량 n 개의 섬 이 있 습 니 다. 우 리 는 해안 에 레이 더 를 키 우 고 레이더 의 커버 반경 은 d 로 정 해 져 있 습 니 다. 적어도 몇 개의 레이 더 를 만들어 야 모든 섬 을 덮 을 수 있 습 니까?
제목 분석: 제목 은 이미 좌표 계 를 세 웠 고 해안 은 x 축 이다. 우리 의 레이 더 는 x 축 에 세 워 진 것 이다. 모든 섬 에 대해 x 축 에 대응 하 는 구간 이 있어 레이 더 를 만들어 서 덮 을 수 있다.우 리 는 먼저 각 섬 이 x 축 에 대응 하 는 구간 을 계산 한 다음 에 구간 을 왼쪽 단점 크기 에 따라 오름차 순 으로 배열 한다.우 리 는 레이 더 를 설치 할 때마다 한 구간 이 있 습 니 다. 이 구간 은 지난번 레이더 배치 구간 (l1, r1) 과 현재 덮어 야 할 섬의 대응 구간 (l2, r2) 사람 이 l2 > r1 이면 레이더 수 에 1 을 더 하기 로 결 정 했 습 니 다. 현재 레이더 배치 구간 은 (l2, r2) 이 고 r2 < r1 이면 레이더 수 는 변 하지 않 으 며 현재 레이더 배치 구간 은 (l1, r2) 으로 변 했 습 니 다. r2 > = r1 이면 레이더 수 는 변 하지 않 습 니 다.현재 레이더 구간 은 변 하지 않 습 니 다.
코드 는 다음 과 같 습 니 다:

public class Main_1328 {
	static int n,d;
	static double[] ll=new double[1001];
	static double[] rr=new double[1001];
	public static void main(String[] args)
	{
		Scanner in=new Scanner(System.in);
		n=in.nextInt();
		d=in.nextInt();
		int cnt=1;
		boolean flag=false;
		while(n!=0||d!=0)
		{
			flag=false;
			int x=0;int y=0;
			for(int i=1;i<=n;i++)
			{
				x=in.nextInt();
				y=in.nextInt();
				ll[i]=x-Math.sqrt(d*d-y*y);
				rr[i]=x+Math.sqrt(d*d-y*y);
				if(y>d || y<-d)
				{
					flag=true;
				}
			}
			if(flag){
				System.out.println("Case "+(cnt++)+": -1");
			}else {

				System.out.print("Case "+(cnt++)+": ");
				solve();
			}
			n=in.nextInt();
			d=in.nextInt();
		}
		
	}
	
	static void solve(){
		
		mergeSort(1, n);
		
		int ans=1;double tmp=rr[1];
		for(int i=2;i<=n;i++){
			if(ll[i]>tmp){
				ans++;
				tmp=rr[i];
			}else if(tmp>rr[i]){
				tmp=rr[i];
			}
		}
		
		System.out.println(ans);
		
	}
	
	// ll[i]    ，           
	static double a[]=new double[1001];
	static double b[]=new double[1001];
	public static void sort(int l,int r)
	{
		if(l==r) return;
		int mid=(l+r)/2;
		for(int i=l;i<=mid;i++)
		{
			a[i]=ll[i];
			b[i]=rr[i];
		}
		for(int i=mid+1;i<=r;i++)
		{
			a[i]=ll[r-i+mid+1];
			b[i]=rr[r-i+mid+1];
		}
		
		int x=l,y=r;
		for(int i=l;i<=r;i++)
		{
			if(a[x]<a[y])
			{
				ll[i]=a[x];
				rr[i]=b[x++];
			}else 
			{
				ll[i]=a[y];
				rr[i]=b[y--];
			}
		}
	}
	public static void mergeSort(int l,int r)
	{
		if(r<=l) return;
		int mid=(l+r)/2;
		mergeSort(l, mid);
		mergeSort(mid+1, r);
		sort(l,r);
	}
}