双向广搜。。。
呃，双向广搜一般都都用了HASH判重，这样可以更快判断两个方向是否重叠了。这道题用了双向的BFS，有效地减少了状态。但代码太长了，不写，贴一个别人的代码。。
#include<iostream>
#include<set>
#include<queue>
#include<algorithm>
using namespace std; typedef __int64 i64; const i64 one = (i64);
const int maxn = << ;
int dx[] = { , ,- , } ;
int dy[] = { , , , - }; struct node
{
i64 bd;
int pos[];
}; node st , ed ; i64 stq[maxn] ,edq[maxn] , sz ,ez ; set<i64> win ;
set<i64>:: iterator it ; bool IsOut( int cx,int cy)
{
return cx < || cy < || cx >= || cy >= ;
} bool IsOn( i64 bd ,int cx, int cy)
{
return bd & ( one<<(cx * + cy) ) ;
} void clr( i64 &bd ,int i)
{
if( ! IsOn( bd , i/ , i%) ) return ;
bd -= one<<i;
} void put( i64 &bd, int i )
{
if(IsOn(bd ,i/ ,i%) ) return ;
bd += one <<i ;
} bool next(node cur, int i,int j , node &son)
{
int t , tx , ty , nx , ny , cx , cy ;
i64 bd = cur.bd;
t = cur.pos[i] , tx = t / , ty = t % ;
nx = tx + dx[j] , ny = ty + dy[j] ;
if( IsOut(nx, ny) ) return false;
if( IsOn (bd , nx, ny) )
{
cx = *nx - tx, cy = *ny - ty;
if( IsOut(cx , cy) || IsOn(bd , cx , cy) ) return false;
clr(cur.bd, tx* + ty);
put(cur.bd, cx* + cy);
cur.pos[i] = cx * + cy;
son = cur;
return true;
}
clr(cur.bd , tx * + ty); put(cur.bd , nx * + ny);
cur.pos[i] = nx * + ny ;
son = cur;
return true;
} void deal(node bgn )
{
int i , j , dep = ;
node cur , son , tail;
queue<node> q; tail.bd = - ;
win.clear(); win.insert(bgn.bd);
q.push(tail); q.push(bgn);
while(!q.empty())
{
cur = q.front(); q.pop();
if( cur.bd == - )
{
if(q.empty()) return ;
q.push(tail); cur = q.front() ; q.pop();
if( ++ dep > ) return ;
}
for(i = ; i < ;++i)
for( j = ;j < ;++j )
if ( next( cur , i , j , son ) )
if( win.find(son.bd) ==win.end() )
{
q.push(son);
win.insert(son.bd);
}
}
} int bbs(i64 x)
{
int l , r ,mid;
l = , r = ez - ;
while(l <= r)
{
mid = ( l + r) / ;
if(edq[ mid ] == x) return mid ;
else if ( x < edq[mid] ) r = mid - ;
else l = mid + ;
}
return -;
} bool can()
{
int i , x[],y[] ,check ;
if(scanf("%d%d%d%d%d%d%d%d",&x[],&y[],&x[],&y[],&x[],&y[],&x[],&y[]) == EOF )
return false;
st.bd = ;
for(i = ; i< ; ++i)
{
-- x[i] , -- y[i] ;
put(st.bd , x[i] * + y[i]);
st.pos[i] = x[i] * + y[i];
} ed.bd = ;
for(i = ; i< ; ++i)
{
scanf("%d%d",&x[i],&y[i]);
-- x[i] , -- y[i];
put(ed.bd , x[i] * + y[i]);
ed.pos[i] = x[i] * + y[i] ;
} sz = ez = ; deal(st);
for(it = win.begin() ; it!=win.end(); it ++ )
stq[sz ++ ] = *it; deal(ed);
for(it = win.begin() ; it!=win.end(); it++)
edq[ez ++ ] = *it ; sort(edq , edq + ez); check = ;
for(i = ; i < sz && !check ; ++i)
if( bbs(stq[i]) !=- )
check = ; if(check)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
return true;
} int main()
{
while(can());
return ;
}