radar.java

来自「PKU中一些数据结构基本算法题的java实现」· Java 代码 · 共 93 行

package PKU.GA;
import java.io.*;
import java.util.*;

/**
 * ID:1328
 * 贪心法
 * 
 * @author yhm
 *
 */
public class Radar {
	
	public static void main(String[] argv){
		seg[] control = new seg[1000];
		
		int cases=0;
		int count=0;
		Scanner stdin = new Scanner(System.in);
		while(true){
			int n=stdin.nextInt();
			int b=stdin.nextInt();
			cases++;
			count=1;
			
			boolean nosolution=false;
			if(n==0)return;
			for(int i=0;i<n;i++){
				control[i]=new seg();
				int x=stdin.nextInt();
				int y=stdin.nextInt();
				if(y>b){nosolution=true;}
				else{
					double fx=Math.sqrt(b*b-y*y);
					control[i].left=x-fx;
					control[i].right = x+fx;
				}
			}
			if(nosolution){
				System.out.println("Case "+cases+": -1");
				continue;
			}
			count = solve(control,n);
			System.out.println("Case "+cases+": "+count);

		}
	}
	
	static int solve(seg[] control,int n){
		Arrays.sort(control,0,n);
		seg current = new seg();
		int num = 1;
		current.left = control[0].left;
		current.right = control[0].right;
		for(int i=0;i<n;i++){
			if(control[i].left.compareTo(current.right)<=0){
				current.left = control[i].left;
				current.right = Math.min(current.right, control[i].right);
			}
			else{
				current.left = control[i].left;
				current.right = control[i].right;
				num++;
			}
		}
		return num;
		
		
	}
}



class seg implements Comparable{
	public Double left;
	public Double right;

	public seg(double left, double right) {
		super();
		this.left = left;
		this.right = right;
	}
	public seg() {
		super();
		this.left = new Double(0);
		this.right = new Double(0);
	}
	public int compareTo(Object r){
		seg o=(seg)r;
		return left.compareTo(o.left);
	}
	
}