弱小和无知不是生存的障碍，傲慢才是。------《三体》
import java.util.Arrays;import java.util.Comparator;import java.util.Scanner;/** * * @author dbdxx * 思路： * 导弹只有两种情况，要么是被1号系统拦截，要么就是2号（废话） * 那么怎么来实现最小代价拦截？ * 根据题目，代价=所有系统工作半径的平方和 * * 意思就是说两个系统半径设置要尽可能小？？？？ * 这样想就很容易想到根据导弹到系统的距离来划分导弹归谁， * 好家伙，刚开始我就这样想的，需要考虑的东西很多，但是！！！才过了3个点，我头炸掉 * 突然想到化学实验讲究的不就是单个变量变就好了吗？ * * 那么就把一部分导弹给1号系统，求出它的最大代价， * 另一部分给2号系统，求出它的最大代码 * 在两个代价结合最小的时候便是答案。 * 但是！！！一部分是那些？？就只能递归了， * 但是又有上一次经验，就想到，要不先对根据“导弹对1号系统的距离”对导弹排个序吧 * 然后就可以专心计算2号系统啦~~~ * * * */public class P1158 {static int x1,y1,x2,y2;//1,2号系统的坐标static int N;//一共有多少个导弹static int [][] nodes;//存放导弹坐标public static void main(String[] args) {Scanner input =new Scanner(System.in);//输入x1=input.nextInt();y1=input.nextInt();x2=input.nextInt();y2=input.nextInt();N=input.nextInt();nodes=new int[N][2];for(int i = 0 ; i < N ; i ++) {nodes[i][0]=input.nextInt();nodes[i][1]=input.nextInt();}//重写排序方法,不知道咋整的，百度别，亲~Arrays.sort(nodes,new Comparator<int []>() {//根据“导弹对1号系统的距离”,不会有人不会算 坐标系点对点的距离吧？？？@Overridepublic int compare(int[] a, int[] b) {//不想写那么多变量。。。。。。return ((a[0]-x1)*(a[0]-x1)+(a[1]-y1)*(a[1]-y1))-((b[0]-x1)*(b[0]-x1)+(b[1]-y1)*(b[1]-y1));}});//ans的值是全部导弹被1号系统拦截的代价int ans=(nodes[N-1][0]-x1)*(nodes[N-1][0]-x1)+(nodes[N-1][1]-y1)*(nodes[N-1][1]-y1);int temp=0;//存放2号系统拦截当前这部分导弹的最大代码//从后往前，从前往后都可以，都算给2号系统的for (int i = N-2; i >= 0; i--) {//x2,y2点到导弹的距离int x=(nodes[i+1][0]-x2)*(nodes[i+1][0]-x2);int y=(nodes[i+1][1]-y2)*(nodes[i+1][1]-y2);int xa=(nodes[i][0]-x1)*(nodes[i][0]-x1);int ya=(nodes[i][1]-y1)*(nodes[i][1]-y1);temp=Math.max(temp, x+y);//当前这个拦截这个导弹的代价，上一部分导弹代价比较ans=Math.min(temp+xa+ya, ans);//总代价}System.out.println(ans);}}