首页 > 代码库 > codeforces 724C

codeforces 724C

2024-08-16 03:37:21   219人阅读

在一个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\n",ansv[i]);130         else puts("-1");131     return 0;132 }
View Code

 

codeforces 724C


联系
我们