[POI2008]Mirror Trap-白红宇

[POI2008]Mirror Trap

阅读量：6217 次

发布时间：2019-06-21

本文共 3707 字，大约阅读时间需要 12 分钟。

题目大意：

　　一个$n(n\le10^5)$个顶点的格点多边形，每条边平行于网格线，每个角度数均为$90^\circ$或$270^\circ$，周长小于$3\times10^5$，每个顶点可以安装激光发射器或接收器，发射（接收）器可以发射（接收）一条向多边形内部的、与网格线成$45^\circ$夹角的射线，射线会在多边形边上发生镜面反射，直到被某个接收器接收。求任意一种发射器与接收器的配对方案。

思路：

　　BZOJ上只要求求出发射器的个数，答案显然就是$\frac n2$。原题需要输出方案，考虑任意一条与网格线成$45^\circ$的斜线上，对于所有点$(x,y)$，$x+y$或$x-y$一定是相等的，由于多边形周长有限，可以预处理出周长上的所有整点，对于$x+y$和$x-y$相等的点排序，暴力模拟镜面反射的过程即可。

1 #include  2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 inline int getint() {  7     register char ch;  8     register bool neg=false;  9     while(!isdigit(ch=getchar())) if(ch=='-') neg=true; 10     register int x=ch^'0'; 11     while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0'); 12     return neg?-x:x; 13 } 14 const int N=1e5; 15 using Point=std::pair
          
           ; 16 int n; 17 Point p[N]; 18 bool vis[N]; 19 std::map
           
             v,dir; 20 std::map
            
             
              > map1,map2; 21 std::pair
              
                dxy(const int &i) { 22 if(p[i].first==p[(i+1)%n].first&&p[i].second==p[(i-1+n)%n].second&&p[i].first
               
                
                 p[(i-1+n)%n].second) return std::make_pair(1,-1); 24 if(p[i].first==p[(i+1)%n].first&&p[i].second==p[(i-1+n)%n].second&&p[i].first>p[(i-1+n)%n].first&&p[i].second>p[(i+1)%n].second) return std::make_pair(-1,-1); 25 if(p[i].first==p[(i-1+n)%n].first&&p[i].second==p[(i+1)%n].second&&p[i].first>p[(i+1)%n].first&&p[i].second
                 
                  p[(i+1)%n].first&&p[i].second>p[(i-1+n)%n].second) return std::make_pair(1,1); 27 if(p[i].first==p[(i+1)%n].first&&p[i].second==p[(i-1+n)%n].second&&p[i].first>p[(i-1+n)%n].first&&p[i].second
                  
                   p[(i+1)%n].second) return std::make_pair(-1,1); 30 return std::make_pair(0,0); 31 } 32 int main() { 33 n=getint(); 34 for(register int i=0;i
                   
                    y?1:-1) { 43 map1[x+y].push_back((Point){x,y}); 44 map2[x-y].push_back((Point){x,y}); 45 if(y!=p[i].second) dir[(Point){x,y}]=1; 46 } 47 } 48 if(p[i].second==p[j].second) { 49 const int &y=p[i].second; 50 for(register int x=p[i].first;x!=p[j].first;x+=p[j].first>x?1:-1) { 51 map1[x+y].push_back((Point){x,y}); 52 map2[x-y].push_back((Point){x,y}); 53 if(x!=p[i].first) dir[(Point){x,y}]=-1; 54 } 55 } 56 } 57 for(auto &p:map1) std::sort(p.second.begin(),p.second.end()); 58 for(auto &p:map2) std::sort(p.second.begin(),p.second.end()); 59 printf("%d\n",n/2); 60 for(register int i=0;i
                    
                     first,dx=1; 67 y=t->second,dy=1; 68 } 69 if(dxy(i)==std::make_pair(1,-1)) { 70 const auto t=std::upper_bound(map1[x+y].begin(),map1[x+y].end(),(Point){x,y}); 71 x=t->first,dx=1; 72 y=t->second,dy=-1; 73 } 74 if(dxy(i)==std::make_pair(-1,-1)) { 75 const auto t=std::lower_bound(map2[x-y].begin(),map2[x-y].end(),(Point){x,y})-1; 76 x=t->first,dx=-1; 77 y=t->second,dy=-1; 78 } 79 if(dxy(i)==std::make_pair(-1,1)) { 80 const auto t=std::lower_bound(map1[x+y].begin(),map1[x+y].end(),(Point){x,y})-1; 81 x=t->first,dx=-1; 82 y=t->second,dy=1; 83 } 84 for(;!v.count((Point){x,y})||std::make_pair(-dx,-dy)!=dxy(v[(Point){x,y}]);) { 85 if(dir[(Point){x,y}]==1) dx=-dx; 86 if(dir[(Point){x,y}]==-1) dy=-dy; 87 if(dx==1&&dy==1) { 88 const auto t=std::upper_bound(map2[x-y].begin(),map2[x-y].end(),(Point){x,y}); 89 x=t->first; 90 y=t->second; 91 } 92 if(dx==1&&dy==-1) { 93 const auto t=std::upper_bound(map1[x+y].begin(),map1[x+y].end(),(Point){x,y}); 94 x=t->first; 95 y=t->second; 96 } 97 if(dx==-1&&dy==-1) { 98 const auto t=std::lower_bound(map2[x-y].begin(),map2[x-y].end(),(Point){x,y})-1; 99 x=t->first;100 y=t->second;101 }102 if(dx==-1&&dy==1) {103 const auto t=std::lower_bound(map1[x+y].begin(),map1[x+y].end(),(Point){x,y})-1;104 x=t->first;105 y=t->second;106 }107 }108 vis[v[(Point){x,y}]]=true;109 printf("%d %d\n",i+1,v[(Point){x,y}]+1);110 }111 return 0;112 }

转载于:https://www.cnblogs.com/skylee03/p/8691814.html

你可能感兴趣的文章

Linux运维之系统性能---vmstat工具分析内存的瓶颈