题目大意：
一个$n(nle10^5)$个顶点的格点多边形，每条边平行于网格线，每个角度数均为$90^circ$或$270^circ$，周长小于$3 imes10^5$，每个顶点可以安装激光发射器或接收器，发射（接收）器可以发射（接收）一条向多边形内部的、与网格线成$45^circ$夹角的射线，射线会在多边形边上发生镜面反射，直到被某个接收器接收。求任意一种发射器与接收器的配对方案。
思路：
BZOJ上只要求求出发射器的个数，答案显然就是$frac n2$。原题需要输出方案，考虑任意一条与网格线成$45^circ$的斜线上，对于所有点$(x,y)$，$x+y$或$x-y$一定是相等的，由于多边形周长有限，可以预处理出周长上的所有整点，对于$x+y$和$x-y$相等的点排序，暴力模拟镜面反射的过程即可。
1 #include<map> 2 #include<cstdio> 3 #include<cctype> 4 #include<vector> 5 #include<algorithm> 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<int,int>; 16 int n; 17 Point p[N]; 18 bool vis[N]; 19 std::map<Point,int> v,dir; 20 std::map<int,std::vector<Point>> map1,map2; 21 std::pair<int,int> 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].first&&p[i].second<p[(i+1)%n].second) return std::make_pair(1,1); 23 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)%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)%n].second) return std::make_pair(-1,1); 26 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)%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); 28 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)%n].second) return std::make_pair(-1,-1); 29 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<n;i++) { 35 const int x=getint(),y=getint(); 36 v[p[i]=(Point){x,y}]=i; 37 } 38 for(register int i=0;i<n;i++) { 39 const int j=(i+1)%n; 40 if(p[i].first==p[j].first) { 41 const int &x=p[i].first; 42 for(register int y=p[i].second;y!=p[j].second;y+=p[j].second>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/2); 60 for(register int i=0;i<n;i++) { 61 if(vis[i]) continue; 62 vis[i]=true; 63 int x=p[i].first,y=p[i].second,dx,dy; 64 if(dxy(i)==std::make_pair(1,1)) { 65 const auto t=std::upper_bound(map2[x-y].begin(),map2[x-y].end(),(Point){x,y}); 66 x=t->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 ",i+1,v[(Point){x,y}]+1); 110 } 111 return 0; 112 }