3208877_ac_454ms_5508k.java

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

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

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

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

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

		while(in.hasNext())
		{
			L = in.nextDouble();
			D = in.nextDouble();
			n = in.nextInt();
			p = new TPoint [n+1];
			for(int i = 0; i < n; i++)
			{
				p[i] = new TPoint(in.nextInt(),in.nextInt());
			}
			Arrays.sort(p,0,n);
			int cnt = 0;
			for(int i = 0; i < n; i++)
			{
				double x = p[i].x;
				double y = p[i].y;
				double X = Math.sqrt(D*D-y*y)+x;
				if(X > L)
				{
					X = L;
				}
				int j = i;
				while(j < n&&Math.hypot((double)p[j].y,X-(double)p[j].x) <= D+eps)
				{
					j++;
				}
				i = j - 1;
				cnt++;
			}
			System.out.println(cnt);
		}
	}
}