题解 P2546 【[POI2008]SZK - Mirror trap】

· · 题解

第一问

物理题，一个点射出的光线只能射到一个点上，由于光路可逆，所以反过来的点也只有一个。因此答案为n\div2。

第二问

模拟题，可以模拟出所有的光线得到匹配。先走一遍路记录边上所有的整点坐标。将图逆时针旋转45\degree使得正方向与光线平行，按照坐标排序。先以x为第一关键字，y为第二关键字排序，求出竖直光线；再以y为第一关键字，x为第二关键字排序，求出竖直光线。

最后在图上走路即可。

#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>

const int MAX=1e6;

struct point
{
    int x,y,ver,num;
};

bool cmp1(point a,point b)
{
    return a.x!=b.x?a.x<b.x:a.y<b.y;//按旋转后的横坐标排序 
}

bool cmp2(point a,point b)
{
    return a.y!=b.y?a.y<b.y:a.x<b.x;//按旋转后的纵坐标排序 
}

int len[MAX];
int next[MAX][2];
point side[MAX];//边上的点 
int n,m,akt,a,b,c,p;

void make_next(int wh)
{
    std::sort(side,side+n,wh?cmp2:cmp1);
    akt=(-1);
    for(int i=0;i<n;++i)
    {
        if ((side[i].ver>=0)&&((side[i].ver&1)!=wh))
        //发现这个点是顶点 凸的方向与扫的方向不同 
        {
            next[side[i].num][wh]=(-side[i].ver/2-1);//便于输出的一个处理 
            continue;//跳过 
        }
        if (akt<0)
        {
            akt=i;
        }
        else
        {   //可以射过光线，配对 
            next[side[akt].num][wh]=side[i].num;
            next[side[i].num][wh]=side[akt].num;
            akt=(-1);
        }
    }
}

void insert()
{
    side[n].x=a-b;//相当于把图形逆时针旋转了45° 
    side[n].y=a+b;
    side[n].ver=(-1);
    side[n].num=n;
    n++;
}

void find(int fr)
{
    p=fr;
    akt=((next[fr][0]>=0)?0:1);
    while(next[p][akt]>=0)//直到找到一个顶点 
    {
        p=next[p][akt];
        akt^=1;//横竖交替走路 
    }
    p=(next[p][akt]*=(-1));
}

int pp(int k)
{
    return k>=0?k:(m-1);
}

int main()
{
    scanf("%d",&m);
    printf("%d\n",m>>1);
    for(int i=0;i<m;++i)
    {
        scanf("%d %d",&a,&b);
        len[i]=a+b;
    }
    c=len[m-1];
    for(int i=m-1;i>=1;--i)
    {
        len[i]-=len[i-1];
    }
    len[0]-=c;//预处理每条边的长度和方向 
    a=0;
    b=0;
    for(int i=0;i<m;++i)//走路 
    {
        if (i%2)//横向的边 
        {
            if (len[i]>0)//往正方向走路 
            {
                for(int j=0;j<len[i];++j)
                {
                    insert();//把点加进去 
                    a++;
                }
                side[n-len[i]].ver=((len[pp(i-1)]>0)?(2*i+1):(2*i));
                //根据走路方向加上这个1，表示旋转后这个点向左或右凸出 
                //否则即为向上或下凸 
            }
            else//往负方向走路 
            {
                for(int j=0;j<-len[i];++j)
                {
                    insert();
                    a--;
                }
                side[n+len[i]].ver=((len[pp(i-1)]<0)?(2*i+1):(2*i));
            }
        }
        else//纵向的边 
        {
            if (len[i]>0)//往正方向走路
            {
                for(int j=0;j<len[i];++j)
                {
                    insert();
                    b++;
                }
                side[n-len[i]].ver=((len[pp(i-1)]>0)?(2*i+1):(2*i));
            }
            else//往负方向走路 
            {
                for(int j=0;j<-len[i];++j)
                {
                    insert();
                    b--;
                }
                side[n+len[i]].ver=((len[pp(i-1)]<0)?(2*i+1):(2*i));
            }
        }
    }
    //连光线 
    make_next(0);
    make_next(1);
    for(int i=0;i<n;++i)
    {
        if ((next[i][0]<0)||(next[i][1]<0))//有一个小于0，是顶点 
        {
            find(i);//找到和它唯一对应的顶点 
            printf("%d %d\n",pp(((next[i][0]<0)?(next[i][0]*(-1)):(next[i][1]*(-1)))-2)+1,pp(p-2)+1);
        }
    }
    return 0;
}