NYOJ-710（贪心）-题目----------------------------------外星人的供给站

本文主要是介绍NYOJ-710（贪心）-题目----------------------------------外星人的供给站，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;public class ProblemJ {private static int N, count;private static double R, x, y, z;// 当前亮点的极光点圆心的范围类public static class Rounds {double leftpoint, rightpoint;public Rounds(double leftpoint, double rightpoint) {this.leftpoint = leftpoint;this.rightpoint = rightpoint;}}public static void main(String[] args) throws IOException {StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));st.nextToken();int t = (int) st.nval;while (t-- > 0) {st.nextToken();N = (int) st.nval;st.nextToken();R = st.nval;Rounds rounds[] = new Rounds[N + 1];for (int i = 0; i < N; i++) {st.nextToken();x = st.nval;st.nextToken();y = st.nval;z = Math.sqrt(R * R - y * y);// 圆心// x-z是圆的圆心范围的左区间，x+z是右区间rounds[i] = new Rounds(x - z, x + z);}// 排序，对所有的圆...根据左区间进行排序，从小到大Rounds temp;for (int i = 0; i < N; i++)for (int j = i + 1; j < N; j++)if (rounds[i].leftpoint > rounds[j].leftpoint) {temp = rounds[i];rounds[i] = rounds[j];rounds[j] = temp;}count = 1;// 排序之后，重叠的圆（范围重叠）可以看作是一个，找出几个不连续的范围段就是需要的最少个圆double rightvalue = rounds[0].rightpoint;for (int i = 1; i < N; i++) {// 后一个范围段的左区间比前一个范围段的右区间大，说明是相离的两个圆，即，需要添加一个圆if (rounds[i].leftpoint > rightvalue) {count++;rightvalue = rounds[i].rightpoint;} else {/** 否则，则说明两种情况* 1、前一个范围段和后一个范围段是有重叠一部分，此时，后一个范围段的右区间最大* 2、前一个范围段完全包含后一个范围段，此时前一个范围段的右区间最大* 所以这里的比较是获取到重叠的范围段最大的右区间* */if (rounds[i].rightpoint < rightvalue) {rightvalue = rounds[i].rightpoint;}}}System.out.println(count);}}
}