本文共 1646 字,大约阅读时间需要 5 分钟。
问题描述小明和朋友们一起去郊外植树,他们带了一些在自己实验室精心研究出的小树苗。 小明和朋友们一共有 n 个人,他们经过精心挑选,在一块空地上每个人挑选了一个适合植树的位置,总共 n 个。 他们准备把自己带的树苗都植下去。 然而,他们遇到了一个困难:有的树苗比较大,而有的位置挨太近,导致两棵树植下去后会撞在一起。 他们将树看成一个圆,圆心在他们找的位置上。如果两棵树对应的圆相交, 这两棵树就不适合同时植下(相切不受影响),称为两棵树冲突。 小明和朋友们决定先合计合计,只将其中的一部分树植下去, 保证没有互相冲突的树。他们同时希望这些树所能覆盖的面积和(圆面积和)最大。输入格式输入的第一行包含一个整数 n ,表示人数,即准备植树的位置数。 接下来 n 行,每行三个整数 x, y, r,表示一棵树在空地上的横、纵坐标和半径。输出格式输出一行包含一个整数,表示在不冲突下可以植树的面积和。由于每棵树的面积都是圆周率的整数倍,请输出答案除以圆周率后的值(应当是一个整数)。样例输入61 1 21 4 21 7 24 1 24 4 24 7 2样例输出12
剪支,邻接矩阵,
public class Plant { public static boolean[][] bool = new boolean[31][31]; static boolean[] vis = new boolean[31]; public static int[] x = new int[31]; public static int[] y = new int[31]; public static int[] r = new int[31]; public static int n = 0, max = -1; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); for (int i = 1; i <= n; i++) { x[i] = sc.nextInt(); y[i] = sc.nextInt(); r[i] = sc.nextInt(); } for (int i = 1; i <= n; i++) { for (int j = i + 1; j <= n; j++) { boolean bo = ((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]) > (r[i] + r[j]) * (r[i] + r[j])); bool[i][j] = bo; bool[j][i] = bo; } } sc.close(); dfs(1); System.out.println(max); } public static void dfs(int step) { if (step > n) { int sum = 0; for (int i = 1; i <= n; i++) { if (vis[i]) { sum += (r[i] * r[i]); } } max = Math.max(sum, max); return; } vis[step] = false; dfs(step + 1); for (int i = 1; i < step; i++) { if (vis[i] && !bool[i][step]) { return; } } vis[step] = true; dfs(step + 1); }}
转载地址:http://vzgwi.baihongyu.com/