Abstract
ural 1163
計(jì)算幾何 狀態(tài)dp 博弈
?
Body
Source
http://acm.timus.ru/problem.aspx?space=1&num=1163
Description
博弈雙方在平面上各有給定的8個(gè)圓（棋子）。雙方依次行動(dòng)，每次可以任意選擇棋盤(pán)上任意一個(gè)自己的圓以任意方向射出，該圓和途中碰到的圓都被清理出棋盤(pán)。若輪到自己行動(dòng)時(shí)沒(méi)有自己的圓留在棋盤(pán)上判負(fù)。問(wèn)誰(shuí)勝誰(shuí)負(fù)。
Solution
很明顯的狀態(tài)dp博弈（不過(guò)似乎貪心反例不好構(gòu)造）。令 f[s, p] 表示棋子的01狀態(tài)為s，當(dāng)前先手為p的先手勝負(fù)情況，則 f[s, p] = !(取OR f[s', !p])，其中s'為所有s能轉(zhuǎn)移到的狀態(tài)。于是關(guān)鍵就是求s'，實(shí)際上也就是求用自己的某個(gè)棋子能夠撞掉的棋子組合的集合。令hit[i]={hit[i][0], hit[i][1], ...}為第i個(gè)棋子在初始狀態(tài)下能撞掉的棋子組合的集合（同樣用01狀態(tài)表示），則當(dāng)前狀態(tài)為s時(shí)，第i個(gè)棋子能撞掉的棋子組合就是s BITAND hit[i][j], j=0, 1, ...，那么枚舉自己所有的棋子i和該棋子能撞掉的所有組合即可，s'=s XOR (s BITAND hit[i][j])。那么轉(zhuǎn)化為求hit[i]。剛開(kāi)始我神鬼莫測(cè)地用了個(gè)掃描線法（見(jiàn)代碼注釋部分），結(jié)果WA15，應(yīng)該是某個(gè)角度會(huì)同時(shí)擦過(guò)2個(gè)或以上棋子，事件點(diǎn)重合，但掃描線仍會(huì)把它們看成兩個(gè)事件點(diǎn)。不過(guò)正確做法思路還是脫胎于掃描線，每個(gè)事件點(diǎn)左旋EPS弧度即可代表該事件點(diǎn)左邊的那一段，看看這個(gè)角度能碰到哪些棋子即可規(guī)避事件點(diǎn)重合的問(wèn)題。
P.S.這題精度很奇妙。我比較懶直接用asin和除法，已經(jīng)預(yù)料到結(jié)果會(huì)坑爹。EPS=1e-8時(shí)WA7，1e-7時(shí)WA1，1e-6時(shí)WA27，1e-5時(shí)通過(guò)。如果是正式比賽，不堪設(shè)想……以后還是得老老實(shí)實(shí)寫(xiě)向量法。
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
;
}
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫(xiě)作最大的動(dòng)力，如果您喜歡我的文章，感覺(jué)我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長(zhǎng)非常感激您！手機(jī)微信長(zhǎng)按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
