3209038_wa.java

北大大牛代码 1240道题的原代码 超级权威

import java.util.*;
import java.math.*;

public class Main
{
	final double eps = 1e-8;

	class TPoint implements Comparable <TPoint>
	{
		double x, y;
		TPoint (double x,double y)
		{
			this.x = x;
			this.y = y;
		}
		public int compareTo(TPoint that)
		{
			if(Math.abs(this.x - that.x) < eps)
				return (int)(Math.abs(that.y) - Math.abs(this.y));
			else
				return (int)(this.x - that.x);
		}
	}
	public static void main(String [] args)
	{
		new Main().run();
	}

	private void run()
	{
		double D;
		int n;
		TPoint [] p;
		int cas = 1;
		Scanner in = new Scanner (System.in);

		while(true)
		{
			n = in.nextInt();
			D = in.nextDouble();
			if(n==0&&D==0)
				break;
			System.out.print("Case "+cas+": ");
			cas++;
			p = new TPoint [n+1];
			for(int i = 0; i < n; i++)
			{
				p[i] = new TPoint(in.nextDouble(),in.nextDouble());
			}
			Arrays.sort(p,0,n);
			int cnt = 0;
			boolean fail = false;
			if(D < 0)
			{
				fail = true;
			}
			if(fail)
			{
				System.out.println("-1");
				continue;
			}
			for(int i = 0; i < n; i++)
			{
				double x = p[i].x;
				double y = p[i].y;
				if(Math.abs(y) > D)
				{
					fail = true;
					break;
				}
				double X = Math.sqrt(D*D-y*y)+x;
				int j = i;
				while(j < n&&Math.hypot(p[j].y,X-p[j].x) <= D+eps)
				{
					j++;
				}
				i = j - 1;
				cnt++;
			}
			System.out.println(fail?"-1":cnt);
		}
	}
}