3208795_wa.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);

		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)
			{
				L = X;
			}
			int j = i;
			while(j < n&&Math.hypot(p[j].y,X-p[j].x) <= D)
			{
				j++;
			}
			i = j - 1;
			cnt++;
		}
		System.out.println(cnt);
	}
}