第一届蓝桥杯国际赛真题/第一届蓝桥杯国际赛真题-捕鱼达人

import java.util.ArrayList;
import java.util.Scanner;


public class 捕鱼达人 {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
       Scanner sc = new Scanner(System.in);
       int row = sc.nextInt();
       int R = sc.nextInt();
       //储存坐标
       int arr[][]=new int[row][2];
       for (int i = 0; i < row; i++) {
    	   for (int j = 0; j < 2; j++) {
			arr[i][j]=sc.nextInt();
		}
		
	   }
       //储存算每个点所能包含的点位置
       int sum[][]=new int[row][row-1];
       
       //记录所能捕到点的个数的最大值
       int max = 0;
       //记住第几行
       int maxRow=0;
       for (int i = 0; i < sum.length; i++) {
       //记录临时储存的最大值
        int maxlinshi = 0;
		for (int j = 0; j < sum.length-1; j++) {
			//取出第一个点进行与其他点比较
			if (i==j+1) {
				continue;
			}else{
				double s = (1.0*arr[i][0]-arr[j+1][0])*(arr[i][0]-arr[j+1][0])+
				(1.0*arr[i][1]-arr[j+1][1])*(arr[i][1]-arr[j+1][1]);
				double zhi = Math.sqrt(s);
				if(zhi<=(R*1.0)){
					sum[i][j]=j+1;
					maxlinshi++;
				}
			}
		}
		if (maxlinshi>max) {
			maxRow=i;
			max=maxlinshi;
		}
	  }
       
       //记录除了最大一网捕的之外还需要捕多少网
       int count = 1;
       //辅助数组
       int fuzhu[]=new int[row];
       for (int i = 0; i < fuzhu.length; i++) {
		fuzhu[i]=i+1;
	   }
       
       //先删除可以最大一网捕的坐标
       fuzhu[maxRow]=0;
       for (int i = 0; i < row-1; i++) {
		  if (sum[maxRow][i]!=0) {
			fuzhu[i+1]=0;
		}
	   }
       //判断其他的还需要几网
    for (int i = 0; i <row; i++) {
		for (int j = 0; j <row-1; j++) {
			if(fuzhu[i]==0){
				continue;
			}else{
				fuzhu[i]=0;
				count++;
				for (int j2 = 0; j2 < row-1; j2++) {
					if (sum[i][j2]!=0) {
						fuzhu[sum[i][j2]+1]=0;
					}
				}
			}
		}
	}
       System.out.println(count);
           
	}	
}