首页 > 代码库 > codeforces 724C
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\n",ansv[i]);130 else puts("-1");131 return 0;132 }
codeforces 724C
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。