Coin Slider | Kyons'Blog 




 
 
 
 



 
 



Coin Slider

题目大意

膜拜一位霓虹大佬%%%%

平面上有一堆不重叠的硬币.
给定硬币的起点和终点,问最多可以把多少个硬币从起点直线移动到终点,且不会与其他硬币碰撞.

解析

状压$dp$+计算几何
一个硬币能否移动的条件为:第$i$枚硬币的起点和终点的连线L,与第$j$个硬币中心的距离$d$是否大于这俩个硬币半径的和.
即$distance(L,O_j)<r_j+r_i$
将每一个硬币是否移动过压缩为$0$和$1$,每次要移动$i_{th}$硬币时,先判断答案这一位是不是$1$.
再根据答案数中的二进制位判断$j_{th}$这个圆是在终点还是起点.
最后再判断能否移动,更新答案即可.

代码如下
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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100 + 10;
const double eps = 1e-5;
const double pi = acos(-1.0);
typedef struct point vec;
struct point {
double x, y;
point() {}
point(double a, double b)
{
x = a, y = b;
}
point operator*(const point& i_T) const
{
return point(x * i_T.x, y * i_T.y);
}
point operator*(double u) const
{
return point(x * u, y * u);
}
point operator/(double u) const
{
return point(x / u, y / u);
}
bool operator>(const point a) const
{
return x == a.x ? y > a.y : x > a.x;
}
point operator-(const point a) const
{
return point(x - a.x, y - a.y);
}
point operator+(const point a) const
{
return point(x + a.x, y + a.y);
}
point operator+(double a) const
{
return point(x + a, y + a);
}
bool operator<(const point a) const
{
return y == a.y ? x < a.x : y < a.y;
}
friend ostream& operator<<(ostream& out, point& a)
{
cout << a.x << ',' << a.y;
return out;
}
friend istream& operator>>(istream& in, point& a)
{
in >> a.x >> a.y;
return in;
}
};
typedef struct Line Segment; //线段Segment
struct Line { //直线
vec a, b;
Line(point _a = point(), point _b = point())
: a(_a)
, b(_b)
{
}
friend istream& operator>>(istream& in, Line& a)
{
cin >> a.a >> a.b;
return in;
}
friend ostream& operator<<(ostream& out, Line& a)
{
out << a.a << ' ' << a.b;
return out;
}
};
struct cirles {
point o;
double r;
cirles(point _o = point(), double _r = 0.0)
: r(_r)
, o(_o)
{
}
point Point(double t) //圆上任意一点
{
return point(o.x + r * cos(t), o.y + r * sin(t));
}
friend istream& operator>>(istream& in, cirles& a)
{
in >> a.o >> a.r;
return in;
}
friend ostream& operator<<(ostream& out, cirles& a)
{
out << a.o << ' ' << a.r;
return out;
}
};
struct ceshi2 {
cirles s, t;
};
int dayu_dengyu(double x, double y)
{
if (fabs(x - y) < eps || x > y)
return 1;
return 0;
}
int zhengfu(double x)
{
if (fabs(x) < eps)
return 0;
return x > 0 ? 1 : -1;
}
double changdu(vec a) //长度
{
return sqrt(a.x * a.x + a.y * a.y);
}
double dianji(vec A, vec B) //点积
{
return A.x * B.x + A.y * B.y;
}
double dian_dao_xianduan(Segment l, point c) //点到线段的距离
{
double L = changdu(l.b - l.a);
double r = dianji(l.b - l.a, c - l.a) / (L * L);

if (zhengfu(r) == -1) {
return changdu(c - l.a);
} else if (dayu_dengyu(r, 1)) {
return changdu(c - l.b);
} else {
double L = r * changdu(l.b - l.a), l2 = changdu(c - l.a);
return sqrt(l2 * l2 - L * L);
}
}
int query(int x)
{
int cnt = 0;
while (x > 0) {
cnt++;
x -= (x & -x);
}
return cnt;
}
int dp[1 << 22], N;
ceshi2 K[MAXN];
int main()
{
cin >> N;
for (int i = 0; i < N; i++) {
cin >> K[i].s.r >> K[i].s.o >> K[i].t.o;
K[i].t.r = K[i].s.r;
}

dp[0] = 1;
for (int msk = 0; msk < (1 << N); msk++)
if (dp[msk])
for (int i = 0; i < N; i++)
if (!(msk & (1 << i))) { //如果硬币被移动过了

//判断其他硬币位置是在s,还是在t
vector<cirles> V;
for (int j = 0; j < N; j++)
if (i != j)
if (msk & (1 << j))
V.push_back(K[j].t);
else
V.push_back(K[j].s);

//判断该硬币能否移动

Line l(K[i].s.o, K[i].t.o);
int ok = 1, n = V.size();
for (int j = 0; j < n; j++) {
double d = dian_dao_xianduan(l, V[j].o);
if (d < K[i].s.r + V[j].r - eps)
ok = 0;
}
if (ok)
dp[msk + (1 << i)] = 1;
}

int ans = 0;
for (int msk = 0; msk < (1 << N); msk++)
if (dp[msk])
ans = max(ans, query(msk));
cout << ans << endl;
return 0;
}

 


 
 
 





 

 


 


 

 

 

 

 
 

 

 

 //删除Valine核心代码库外链调用 //调用刚下载的本地文件以加速加载速度 //这里改为从本地加载