Intel Code Challenge Final Round (Div. 1 + Div. 2, Combined)

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

C 模拟

题意：给的是一个矩形，然后√2 的速度走，如果走到边上就正常反射，走到角上，暂停反射，我们知道要不循环要不暂停，记录走到的点最短时间

/*************************************************************************
> File Name: c.cpp
> Author: opas_chenxin
> Mail: 1017370773@qq.com
> Created Time: 2016年10月08日星期六 22时01分54秒
************************************************************************/
#include<stdio.h>
#include<string.h>
#include<map>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;
struct point{
ll x,y,d;
point(ll x1 = , ll y1 = , ll d1 = ) {
x = x1; y = y1; d = d1;
}
bool operator < (point const&A) const{
if(x != A.x) return x < A.x;
if(y != A.y) return y < A.y;
return d < A.d;
}
//bool operator == (point &A){
// return x == A.x && y == A.y && d == A.d;
//}
};
map<point,ll> G;
ll n,m,k;
ll edg_w[]={,,,};
bool GetNextPoint(int loc, point A, ll &t, point &B, int fu) {
ll b = A.y - A.d * A.x;
if(loc&) {
B.y = edg_w[loc];
B.x = (B.y - b) * A.d;
t = abs(A.y - edg_w[loc]);
} else {
B.x = edg_w[loc];
B.y = B.x * A.d + b;
t = abs(A.x - edg_w[loc]);
}
B.d = A.d * fu;
if(B.x < || B.x > n || B.y < || B.y > m || (B.x == A.x && B.y == A.y) )
return false;
return true;
}
point GetNextLoc(point &A, ll &t ) {
point next_loc;
ll tt;
for(int i = ; i < ; ++ i) {
if(GetNextPoint(i, A, tt, next_loc, -)) {
t += tt;
return next_loc;
}
}
return next_loc;
}
bool JudEnd(point &A){
if(A.x == && A.y == ) return true;
if(A.x == && A.y == m) return true;
if(A.x == n && A.y == ) return true;
if(A.x == n && A.y == m) return true;
return false;
}
ll GetAns(point &A){
ll t=;
ll ans = -;
for(int i = ; i < ; ++ i) {
A.d = -A.d;
for(int j = ; j < ; ++ j) {
point B;
if(GetNextPoint(j, A, t, B, )) {
if(G.count(B) > ) {
if(ans == -)
ans = G[B]+t;
else
ans = min(G[B]+t, ans);
}
}
}
}
if(ans != -) ans = ans -;
return ans;
}
int main() {
freopen("in", "r", stdin);
while( cin>>n>>m>>k ) {
edg_w[] = n;
edg_w[] = m;
G.clear();
point now = point(,,);
ll t = ;
G.insert(pair<point,ll>(now,t));
while(true) {
point next_loc = GetNextLoc(now, t);
if(JudEnd(next_loc)) break;
if(G.count(next_loc) > ) break;
else G.insert(pair<point,ll>(next_loc,t));
now = next_loc;
G.insert(pair<point,ll>(now,t));
}
for(int i = ; i < k; ++ i) {
ll x, y;
cin>>x>>y;
point A = point(x, y, );
cout<<GetAns(A)<<endl;
}
}
return ;
}