1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
| #include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>
#include <cmath>
#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
struct P {
int x, y, r, c;
P() : x(0), y(0), r(0), c(0) {}
P(int x, int y, int r, int c) : x(x), y(y), r(r), c(c) {}
};
int n, ans;
vector<P> v;
set<int> memo;
void dfs(int S) {
if(memo.find(S) != memo.end()) return;
memo.insert(S);
ans = max(ans, __builtin_popcount(S));
if(ans == n) return;
bool up[50];
memset(up, 0, sizeof(up));
for(int i = n-1; i >= 0; i--) {
if(S & (1<<i)) continue;
bool flag = true;
for(int j = i-1; j >= 0; j--) {
if(S & (1<<j)) continue;
int dist = (v[j].x - v[i].x) * (v[j].x - v[i].x) + (v[j].y - v[i].y) * (v[j].y - v[i].y);
int len = (v[i].r + v[j].r) * (v[i].r + v[j].r);
if(dist < len) {
flag = false;
}
}
if(!flag) up[i] = true;
}
set<int> st[5];
for(int i = n-1; i >= 0; i--) {
if((S & (1<<i)) || up[i]) continue;
bool flag = true;
for(int j = i-1; j >= 0; j--) {
if((S & (1<<j)) || up[j]) continue;
int dist = (v[j].x - v[i].x) * (v[j].x - v[i].x) + (v[j].y - v[i].y) * (v[j].y - v[i].y);
int len = (v[i].r + v[j].r) * (v[i].r + v[j].r);
if(dist >= len && v[i].c == v[j].c) {
dfs(S + (1<<i) + (1<<j));
}
}
}
}
int main() {
while(cin >> n && n) {
v.clear();
memo.clear();
rep(i, n) {
int x, y, r, c;
cin >> x >> y >> r >> c;
v.push_back(P(x, y, r, c));
}
vector<bool> used(n);
rep(i, n) used[i] = false;
ans = 0;
int S = 0;
dfs(S);
cout << ans << endl;
}
return 0;
}
|