Abstract
ural 1163
计算几何 状态dp 博弈
Body
Source
http://acm.timus.ru/problem.aspx?space=1&num=1163
Description
博弈双方在平面上各有给定的8个圆（棋子）。双方依次行动，每次可以任意选择棋盘上任意一个自己的圆以任意方向射出，该圆和途中碰到的圆都被清理出棋盘。若轮到自己行动时没有自己的圆留在棋盘上判负。问谁胜谁负。
Solution
很明显的状态dp博弈（不过似乎贪心反例不好构造）。令 f[s, p] 表示棋子的01状态为s，当前先手为p的先手胜负情况，则 f[s, p] = !(取OR f[s', !p])，其中s'为所有s能转移到的状态。于是关键就是求s'，实际上也就是求用自己的某个棋子能够撞掉的棋子组合的集合。令hit[i]={hit[i][0], hit[i][1], ...}为第i个棋子在初始状态下能撞掉的棋子组合的集合（同样用01状态表示），则当前状态为s时，第i个棋子能撞掉的棋子组合就是s BITAND hit[i][j], j=0, 1, ...，那么枚举自己所有的棋子i和该棋子能撞掉的所有组合即可，s'=s XOR (s BITAND hit[i][j])。那么转化为求hit[i]。刚开始我神鬼莫测地用了个扫描线法（见代码注释部分），结果WA15，应该是某个角度会同时擦过2个或以上棋子，事件点重合，但扫描线仍会把它们看成两个事件点。不过正确做法思路还是脱胎于扫描线，每个事件点左旋EPS弧度即可代表该事件点左边的那一段，看看这个角度能碰到哪些棋子即可规避事件点重合的问题。
P.S.这题精度很奇妙。我比较懒直接用asin和除法，已经预料到结果会坑爹。EPS=1e-8时WA7，1e-7时WA1，1e-6时WA27，1e-5时通过。如果是正式比赛，不堪设想……以后还是得老老实实写向量法。
Code
#include <cassert>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
using
namespace
std;
const
double
EPS = 1e-
5
;
const
double
PI = acos(-
1.0
);
const
double
R =
0.4
;
inline
int
dcmp(
double
d)
{
if
(fabs(d)<EPS)
return
0
;
return
d>
0
?
1
:-
1
;
}
struct
sp
{
double
x, y;
sp() {}
sp(
double
a,
double
b): x(a), y(b) {}
void
read() {scanf(
"
%lf%lf
"
, &x, &y);}
}p[
20
];
inline sp
operator
-(
const
sp &u,
const
sp &v)
{
return
sp(u.x-v.x, u.y-v.y);}
inline
double
dis(
const
sp &u,
const
sp &v)
{
double
dx = u.x-v.x;
double
dy = u.y-v.y;
return
sqrt(dx*dx+dy*dy);
}
double
pa(
const
sp &o,
const
sp &p)
{
return
atan2(p.y-o.y, p.x-o.x);}
struct
snode
{
double
a;
int
s;
snode() {}
snode(
double
x,
int
y): a(x), s(y) {}
};
bool
operator
<(
const
snode &u,
const
snode &v)
{
if
(dcmp(u.a-v.a)==
0
)
return
u.s>v.s;
return
u.a<v.a;
}
inline
bool
between(
double
a,
double
s,
double
t)
{
return
dcmp(a-s)>
0
&&dcmp(a-t)<
0
;}
inline
bool
inside(
double
a,
double
s,
double
t)
{
return
between(a, s, t)||between(a+
2
*PI, s, t)||between(a-
2
*PI, s, t);}
double
rgl(
double
a)
{
if
(a<-PI)
return
a+
2
*PI;
if
(a>PI)
return
a-
2
*PI;
return
a;
}
double
as
[
20
], at[
20
];
vector<
int
> hit[
20
];
vector<snode> node;
int
f[
1
<<
16
][
2
];
int
dfs(
int
s,
int
p)
{
if
(f[s][p]>=
0
)
return
f[s][p];
int
d = p*
8
;
int
res =
0
;
for
(
int
i = d; i < d+
8
; ++i)
{
if
(!(s&(
1
<<i)))
continue
;
for
(
int
j =
0
; j < hit[i].size(); ++j)
res |= !dfs(s^(s&hit[i][j]), !p);
}
return
f[s][p] = res;
}
int
main()
{
int
i, j, k;
for
(i =
0
; i <
8
; ++i)
p[i].read();
for
(i =
8
; i <
16
; ++i)
p[i].read();
for
(i =
0
; i <
16
; ++i)
{
//
node.clear();
for
(j =
0
; j <
16
; ++j)
{
if
(i==j)
continue
;
double
a = pa(p[i], p[j]);
double
da = asin(R/(dis(p[i], p[j])/
2
));
as
[j] = a-da; at[j] = a+da;
/*
node.push_back(snode(rgl(as[j]), 1<<j));
node.push_back(snode(rgl(at[j]), -(1<<j)));
*/
}
for
(j =
0
; j <
16
; ++j)
{
if
(i==j)
continue
;
int
s =
1
<<i;
for
(k =
0
; k <
16
; ++k)
if
(i!=k && inside(
as
[j]+EPS,
as
[k], at[k])) s |=
1
<<k;
hit[i].push_back(s);
s =
1
<<i;
for
(k =
0
; k <
16
; ++k)
if
(i!=k && inside(at[j]+EPS,
as
[k], at[k])) s |=
1
<<k;
hit[i].push_back(s);
}
/*
int s = 0;
for (j = 0; j < 16; ++j)
{
if (i==j) continue;
if (inside(-PI, as[j], at[j])) s += 1<<j;
}
if (s)
{
node.push_back(snode(-PI-EPS, s));
node.push_back(snode(PI+EPS, -s));
}
sort(node.begin(), node.end());
s = 1<<i;
for (j = 0; j < node.size(); ++j)
{
s += node[j].s;
assert(s>=(1<<i) && s<(1<<16));
hit[i].push_back(s);
}
*/
}
memset(f,
255
,
sizeof
(f));
for
(
int
s =
0
; s <
1
<<
16
; ++s)
{
if
(!(s&
255
)) f[s][
0
] =
0
;
if
(!(s&
65280
)) f[s][
1
] =
0
;
}
if
(dfs((
1
<<
16
)-
1
,
0
)) puts(
"
RED
"
);
else
puts(
"
WHITE
"
);
return
0
;
}
