codeforces 724C

在一个nxm的镜面二维空间内，向(1,1)发射一条射线，来回反射，当遇到四个角之一时光线消失。

给K个点，问K个点第一次被射中是什么时候（v = sqrt(2)）

解：注意到只有 2*(n+m)个对角线，从而从(1,1)发射光线后，最多折射O(n)此。

只需要模拟光线的折射即可。

具体实现时，记录光线的起点，终点。记录直线方程（截距和斜率的正负）

每一次用上一个终点和直线方程算出新的光线的终点。

（分为2*2*2 = 8种情况讨论）

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <iostream>
  4 #include <cstdlib>
  5 #include <ctime>
  6 #include <cmath>
  7 #include <algorithm>
  8 #include <set>
  9 #include <map>
 10 #include <queue>
 11 #include <vector>
 12 
 13 #define N 100010
 14 #define INF 0x3f3f3f3f3f3f3f3fLL
 15 #define LL long long
 16 
 17 using namespace std;
 18 
 19 struct node{
 20     int x,y,id;
 21     void scan(int i){
 22         id=i;
 23         scanf("%d%d",&x,&y);
 24     }
 25 }a[N];
 26 
 27 struct line{
 28     node S,T;
 29     int typ,t;
 30 }b[N];
 31 
 32 int n,m,K;
 33 LL ansv[N];
 34 vector<node> A[2][2*N];
 35 queue<line> q;
 36 bool vis[2][2*N];
 37 
 38 int Abs(int x){
 39     if(x<0) return -x;
 40     return x;
 41 }
 42 
 43 void update_min(LL &a,LL b){
 44     if(b<a) a=b;
 45 }
 46 
 47 bool get_next(line now){
 48     if((now.T.x==0||now.T.x==n) && (now.T.y==0||now.T.y==m)) return 0;
 49     line ans;
 50     ans.S=now.T;
 51     ans.typ=now.typ^1;
 52 
 53     if(ans.typ==0){
 54         ans.t = ans.S.x+ans.S.y;
 55         
 56         if(now.S.x < now.T.x){
 57             if(now.T.y == m){
 58                 if(ans.t-n >= 0) ans.T = (node){n,ans.t-n};
 59                 else ans.T = (node){ans.t,0};
 60             }
 61             else ans.T = (node){ans.t-m,m};
 62         }
 63         else{
 64             if(now.T.y == 0){
 65                 if(ans.t <= m) ans.T = (node){0,ans.t};
 66                 else ans.T = (node){ans.t-m,m};
 67             }
 68             else ans.T = (node){ans.t,0};
 69         }
 70     }
 71 
 72     else{
 73         ans.t = ans.S.y-ans.S.x+n;
 74         
 75         if(now.S.x < now.T.x){
 76             if(now.T.y == 0){
 77                 if(ans.t <= m) ans.T = (node){n,ans.t};
 78                 else ans.T = (node){m+n-ans.t,m};
 79             }
 80             else ans.T = (node){n-ans.t,0};
 81         }
 82         else{
 83             if(now.T.y == m){
 84                 if(ans.t <= n) ans.T = (node){n-ans.t,0};
 85                 else ans.T = (node){0,ans.t-n};
 86             }
 87             else ans.T = (node){m+n-ans.t,m};
 88         }
 89     }
 90 //    cout << "node " << ans.T.x << ' ' << ans.T.y << endl;
 91 //    cout << ans.typ << ' ' << ans.t << endl;
 92     if(vis[ans.typ][ans.t]) return 0;
 93     q.push(ans);
 94     return 1;
 95 }
 96 
 97 int main(){
 98 //    freopen("test.txt","r",stdin);
 99     scanf("%d%d%d",&n,&m,&K);
100     for(int i=1;i<=K;i++) a[i].scan(i);
101     if(n<m){
102         swap(n,m);
103         for(int i=1;i<=K;i++)
104             swap(a[i].x,a[i].y);
105     }
106     
107     for(int i=1;i<=K;i++){
108         A[0][a[i].x+a[i].y].push_back(a[i]);
109         A[1][a[i].y-a[i].x+n].push_back(a[i]);
110         ansv[i]=INF;
111     }
112     
113     vis[1][n]=1;
114     q.push((line){(node){0,0,0}, (node){m,m,0}, 1 ,n});
115     LL ansnow=0;
116     
117     while(!q.empty()){
118         line tmp=q.front(); q.pop();
119         
120         vector<node> &now = A[tmp.typ][tmp.t];
121         for(int i=0,ln=now.size();i<ln;i++)
122             update_min(ansv[now[i].id], ansnow + (LL)Abs(now[i].x-tmp.S.x) );
123         
124         ansnow += (LL)Abs(tmp.T.x-tmp.S.x);
125         if(!get_next(tmp)) break;
126     }
127     
128     for(int i=1;i<=K;i++)
129         if(ansv[i]!=INF) printf("%I64d
",ansv[i]);
130         else puts("-1");
131     return 0;
132 }

View Code