POJ 1328 Radar Installation

問題

1328 -- Radar Installation

蟻本の練習問題埋めの一環として取り組んだ。
制約書いてないのがあったりして混乱したので解説記事をみて通した。
幾何的要素が若干あったので、色々理解するのに時間がかかった。

考察

レーダーの適用範囲を円とし、その円の中心をレーダーの座標位置とする。

島からレーダーの座標位置までの最大距離はDなので、レーダーの座標位置は(島の座標位置) = とするとになる。(三平方の定理から)

島の座標位置の中にを満たすものがある場合は必ずレーダーの適用範囲外になる

座標の値を昇順に島の座標位置をソートする。

ソート後の島を見ていき、出来るだけ一つのレーダーの適用範囲内に多く島の座標位置が内包するようにレーダーの座標位置を調節していく。

参考：
Radar Installation | Algorithm Notes

POJ 1328 Radar Installation greedy

ソースコード

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.NoSuchElementException;

public class Main {
	int N,D;
	P[] points;

	private class P implements Comparable<P>{
		int x,y;
		public P(int x,int y){
			this.x = x;
			this.y = y;
		}

		public int compareTo(P p){
			if(this.x == p.x){
				return this.y - p.y;
			}
			return this.x - p.x;
		}
	}

	public boolean check(){
		for(int i = 0;i < N;i++){
			if(points[i].y > D){
				return false;
			}
		}
		return true;
	}

	public void solve() {
		int cnt = 1;

		while(true){
			N = nextInt();
			D = nextInt();

			if(N + D == 0)break;

			points = new P[N];

			for(int i = 0;i < N;i++){
				int x = nextInt();
				int y = nextInt();
				points[i] = new P(x,y);
			}

			Arrays.sort(points);

			int ans = 1;

                        //y > Dをチェック
			if(!check()){
				out.println("Case " + cnt + ": " + "-1");
			}else{
				double X = points[0].x;
				double Y = points[0].y;
　　　　　　　　　　　　　　　　//現在のレーダーの座標位置
				double radarX = X + Math.sqrt(D * D - Y * Y);

				for(int i = 1;i < N;i++){
					int x = points[i].x;
					int y = points[i].y;

                                        //最低でもpointLeftにレーダーを設置すれば島iを適用範囲に内包可能
					double pointLeft = x - Math.sqrt(D * D - y * y);
                                        
                                        //現在のレーダーの座標位置から島iを適用範囲内に設置できるか
					if(pointLeft > radarX){
						X = points[i].x;
						Y = points[i].y;
　　　　　　　　　　　　　　　　　　　　　　　　//現在のレーダーの座標位置を更新
						radarX = X + Math.sqrt(D * D - Y * Y);
						ans++;
					}else{
　　　　　　　　　　　　　　　　　　　　　　　　//出来るだけxを値を小さくしないとpoints[i].x < points[i + 1].x && points[i].y < points[i + 1].yのケースで落ちる 
						radarX = Math.min(radarX, x + Math.sqrt(D * D - y * y));
					}
				}

				out.println("Case " + cnt + ": " + ans);
			}

			cnt++;
		}
	}

	public static void main(String[] args) {
		out.flush();
		new Main().solve();
		out.close();
	}

	/* Input */
	private static final InputStream in = System.in;
	private static final PrintWriter out = new PrintWriter(System.out);
	private final byte[] buffer = new byte[2048];
	private int p = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (p < buflen)
			return true;
		p = 0;
		try {
			buflen = in.read(buffer);
		} catch (IOException e) {
			e.printStackTrace();
		}
		if (buflen <= 0)
			return false;
		return true;
	}

	public boolean hasNext() {
		while (hasNextByte() && !isPrint(buffer[p])) {
			p++;
		}
		return hasNextByte();
	}

	private boolean isPrint(int ch) {
		if (ch >= '!' && ch <= '~')
			return true;
		return false;
	}

	private int nextByte() {
		if (!hasNextByte())
			return -1;
		return buffer[p++];
	}

	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = -1;
		while (isPrint((b = nextByte()))) {
			sb.appendCodePoint(b);
		}
		return sb.toString();
	}

	public int nextInt() {
		return Integer.parseInt(next());
	}

	public long nextLong() {
		return Long.parseLong(next());
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}
}