[USACO 2014 Gold] Cow Optics

作法：

考慮從起點發射出去的光線，那麼新放的鏡子一定會落在這條光線上，否則就沒辦法改變這條光的行進路線了。於是這條光線打到新放的鏡子之後會走到終點，所以反過來看的話，就可以得到從終點往某一個方向發射出去的光線也會通過新放的鏡子，因此可以得到新放的鏡子的所有位置：把起點射出的光線路徑找出來，還有從終點射出的四個方向的路徑都找出來，然後求他們有幾個交點就可以了。

但實作上還蠻麻煩的，首先把問題拆成兩個部份，第一個是找出所有的路徑上的線段，第二個則是求出所有直的和橫的的線段有幾個交點。先看第二個部份，我們把所有直的線段的上下兩端點都看成一次事件，分別會把橫座標的這個位置的值+1或-1，然後從低到高考慮橫的線段，在作一條線段之前先把所有在他之前發生的事件都加進去，那麼目前這條橫的線段上的交點數就會是這條線段覆蓋到的區間上的數字總和，所以這裡可以先離散化之後用 BIT 求出答案。

第一個部份比較麻煩，首先我們要知道從一個點開始往某一個方向進行的光線會打到哪個點，而如果打不到任何鏡子的話就必須回傳一個足夠遠的點。這個部份可以用 map<int,vector<int>> 實作，對於每個 x 座標，可以紀錄有哪些點的 x 座標是他，並且把他們按照 y 座標大小排序，就可以對他二分搜了。 y 座標也同理。比較麻煩的是，由題目給的範測可以發現，在找從終點出發的四條光線的路徑的時候，有可能會產生循環，這代表我們還必須判斷：如果目前光線所在的點和他即將到達的點上，經過了光線的起點（也就是原始題目給的終點），那麼就要把新得到的點改成光線起點，然後趕快退出。另外一點則是有可能算到兩次一模一樣的路徑，而我的解決方法是當在取的路徑的時候，如果他返回了光線的原點，那就回傳他是從哪個方向回去的，並且標記已經走過了，這樣之後就不會再走到了。

對了還要注意到一點，就是 ( 0,0 ) 不能出現在終點發出的光線中，而避免這件事的方法就只要把 ( 0,0 ) 也當作已經放好的鏡子就好了，但如果新找到的點就是 ( 0,0 ) 的話也要 break 掉，因為他並不反射任何光線。

code :

#include<bits/stdc++.h>
#define INF 1100000000
#define lowbit(x) (x&-x)
#define LL long long
#define F first
#define S second
using namespace std;
const int maxn=100000+10 ;
 
int bit[2*maxn] ;
void add(int x,int val)
{
    while(x<2*maxn) bit[x]+=val , x+=lowbit(x) ;
}
 
int query(int l,int r)
{
    l-- ;
    int ret=0 ;
    while(r) ret+=bit[r] , r-=lowbit(r) ;
    while(l) ret-=bit[l] , l-=lowbit(l) ;
    return ret ;
}
 
struct seg
{
    int x1,y1,x2,y2 ;
    bool operator < (const seg &rhs) const
    {
        return y1<rhs.y1 ;
    }
};
 
struct event
{
    int t,pos,val ;
    bool operator < (const event &rhs) const
    {
        return t<rhs.t ;
    }
}eve[2*maxn];
 
vector<int> tv ;
LL cal(vector<seg> &ver,vector<seg> &hor)
{
    if(ver.empty() || hor.empty()) return 0LL ;
    memset(bit,0,sizeof(bit)) ;
    tv.clear() ;
    for(auto i : ver) tv.push_back(i.x1) ;
    for(auto i : hor)
        tv.push_back(i.x1) ,
        tv.push_back(i.x2) ;
    sort(tv.begin(),tv.end()) ;
    tv.resize(unique(tv.begin(),tv.end())-tv.begin()) ;
 
    int ecnt=0 ;
    for(auto i : ver)
    {
        int x=lower_bound(tv.begin(),tv.end(),i.x1)-tv.begin() ;
        x++ ;
        int y1=min(i.y1,i.y2) , y2=max(i.y1,i.y2) ;
        eve[ecnt++]=(event){y1,x,1} ;
        eve[ecnt++]=(event){y2,x,-1} ;
    }
    sort(eve,eve+ecnt) ;
    sort(hor.begin(),hor.end()) ;
 
    LL ans=0LL ;
    int j=0 ;
    for(auto i : hor)
    {
        while(j<ecnt && eve[j].t<i.y1)
        {
            add(eve[j].pos,eve[j].val) ;
            j++ ;
        }
        int x1=lower_bound(tv.begin(),tv.end(),i.x1)-tv.begin() ;
        int x2=lower_bound(tv.begin(),tv.end(),i.x2)-tv.begin() ;
        x1++ ; x2++ ;
        if(x1>x2) swap(x1,x2) ;
        ans+=query(x1,x2) ;
    }
    return ans ;
}
 
struct pt
{
    int x,y,type ; /// type=1 : \ , type=2 : /
    bool operator < (const pt &rhs) const
    {
        return x==rhs.x ? y<rhs.y : x<rhs.x ;
    }
};
 
map<int,vector<pt> > mph,mpv ;
pt getpt(const pt &p,int dir) /// 1~4 : up , down , left , right
{
    if(dir<=2)
    {
        auto it=mpv.find(p.x) ;
        int id ;
        if(dir==1) id=upper_bound(it->S.begin(),
                    it->S.end(),p)-it->S.begin() ;
        else id=lower_bound(it->S.begin(),
                    it->S.end(),p)-it->S.begin()-1 ;
        if(id<it->S.size() && id>=0) return it->S[id] ;
        pt ret ;
        ret.type=-1 ; ret.x=p.x ;
        ret.y= dir==1 ? INF : -INF ;
        return ret ;
    }
    else
    {
        auto it=mph.find(p.y) ;
        int id ;
        if(dir==4) id=upper_bound(it->S.begin(),
                    it->S.end(),p)-it->S.begin() ;
        else id=lower_bound(it->S.begin(),
                    it->S.end(),p)-it->S.begin()-1 ;
        if(id<it->S.size() && id>=0) return it->S[id] ;
        pt ret ;
        ret.type=-1 ; ret.y=p.y ;
        ret.x= (dir==4 ? INF : -INF) ;
        return ret ;
    }
}
 
bool on_seg(const pt &p,const pt &a,const pt &b)
{
    if(a.x==b.x) return p.x==a.x &&
        (LL)(p.y-a.y)*(p.y-b.y)<0 ;
    else return p.y==a.y &&
        (LL)(p.x-a.x)*(p.x-b.x)<0 ;
}
 
int getpath(pt st,int dir,vector<seg> &pth)
{
    pt now=st ;
    while(1)
    {
        pt newp=getpt(now,dir) ;
        if(on_seg(st,now,newp))
        {
            pth.push_back((seg){now.x,now.y,st.x,st.y}) ;
            if(dir<=2) return 3-dir ;
            else return 7-dir ;
        }
 
        pth.push_back((seg){now.x,now.y,newp.x,newp.y}) ;
        if(newp.type>0)
        {
            if(newp.type==2) dir=5-dir ;
            else if(dir%2) dir=4-dir ;
            else dir=6-dir ;
            now=newp ;
        }
        else return -1 ;
    }
}
 
vector<seg> pst,ped ;
vector<seg> v1,v2,h1,h2 ;
LL solve(const pt &ed)
{
    getpath((pt){0,0,-1},1,pst) ;
    bool ok[5] ; memset(ok,0,sizeof(ok)) ;
    for(int i=1;i<5;i++) if(!ok[i])
    {
        int res=getpath(ed,i,ped) ;
        if(res!=-1) ok[res]=1 ;
    }
 
    for(auto i : pst)
    {
        if(i.x1==i.x2) v1.push_back(i) ;
        else h2.push_back(i) ;
    }
    for(auto i : ped)
    {
        if(i.x1==i.x2) v2.push_back(i) ;
        else h1.push_back(i) ;
    }
    return cal(v1,h1)+cal(v2,h2) ;
}
 
main()
{
    if(fopen("optics.in","r"))
    {
        freopen("optics.in","r",stdin) ;
        freopen("optics.out","w",stdout) ;
    }
    int n,ex,ey ; scanf("%d%d%d",&n,&ex,&ey) ;
    while(n--)
    {
        pt p ; char s[5] ;
        scanf("%d%d%s",&p.x,&p.y,s) ;
        if(s[0]=='\\') p.type=1 ;
        else p.type=2 ;
        mph[p.y].push_back(p) ;
        mpv[p.x].push_back(p) ;
    }
    mph[0].push_back((pt){0,0,-1}) ;
    mpv[0].push_back((pt){0,0,-1}) ;
    for(auto &i : mph) sort(i.S.begin(),i.S.end()) ;
    for(auto &i : mpv) sort(i.S.begin(),i.S.end()) ;
 
    printf("%lld\n",solve((pt){ex,ey,-1})) ;
}