fork download
copy 
  1. import java.util.*;
  2.  
  3. class D {
  4.  
  5. 	public void run() {
  6. 		Scanner sc = new Scanner(System.in);
  7. 		for (int n = sc.nextInt(); n > 0; n = sc.nextInt()) {
  8. 			int[] x = new int[n];
  9. 			int[] y = new int[n];
  10. 			int[] r = new int[n];
  11. 			int[] c = new int[n];
  12. 			for (int i = 0; i < n; i++) {
  13. 				x[i] = sc.nextInt();
  14. 				y[i] = sc.nextInt();
  15. 				r[i] = sc.nextInt();
  16. 				c[i] = sc.nextInt();
  17. 			}
  18. 			boolean[][] on = new boolean[n][n];
  19. 			for (int i = 0; i < n; i++)
  20. 				for (int j = 0; j < i; j++)
  21. 					on[i][j] = check(x[i] - x[j], y[i] - y[j], r[i] + r[j]);
  22. 			boolean[] left = new boolean[n];
  23. 			for (int i = 0; i < n; i++)
  24. 				left[i] = true;
  25. 			map.clear();
  26. 			System.out.println(dfs(n, on, c, left));
  27. 		}
  28. 	}
  29.  
  30. 	private Map<Integer, Integer> map = new HashMap<Integer, Integer>();
  31.  
  32. 	private int dfs(int n, boolean[][] on, int[] c, boolean[] left) {
  33. 		int key = toi(left);
  34. 		if (map.containsKey(key))
  35. 			return map.get(key);
  36. 		int max = 0;
  37. 		loop1: for (int i = 0; i < n; i++)
  38. 			if (left[i]) {
  39. 				for (int k = 0; k < i; k++)
  40. 					if (left[k] && on[i][k])
  41. 						continue loop1;
  42. 				loop2: for (int j = 0; j < n; j++)
  43. 					if (left[j] && i != j && c[i] == c[j]) {
  44. 						for (int k = 0; k < j; k++)
  45. 							if (left[k] && on[j][k])
  46. 								continue loop2;
  47. 						left[i] = left[j] = false;
  48. 						max = Math.max(max, 2 + dfs(n, on, c, left));
  49. 						left[i] = left[j] = true;
  50. 					}
  51. 			}
  52. 		map.put(key, max);
  53. 		return max;
  54. 	}
  55.  
  56. 	int toi(boolean[] bs) {
  57. 		int ret = 0;
  58. 		for (boolean b : bs) {
  59. 			ret <<= 1;
  60. 			if (b)
  61. 				ret++;
  62. 		}
  63. 		return ret;
  64. 	}
  65.  
  66. 	boolean check(int dx, int dy, int rr) {
  67. 		return dx * dx + dy * dy < rr * rr;
  68. 	}
  69.  
  70. 	public static void main(String[] args) throws Exception {
  71. 		new D().run();
  72. 	}
  73. }
Success #stdin #stdout 0.07s 213888KB
comments (?)
stdin
copy 
4
0 0 50 1
0 0 50 2
100 0 50 1
0 0 100 2
7
12 40 8 1
10 40 10 2
30 40 10 2
10 10 10 1
20 10 9 3
30 10 8 3
40 10 7 3
2
0 0 100 1
100 32 5 1
0
stdout
copy 
2
4
0
https://ideone.com/m5mzo
language:
Java (HotSpot 12)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!