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
;
}
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
