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

C. Ray Tracing

There are k sensors located in the rectangular room of size n × m meters. The i-th sensor is located at point (xi, yi). All sensors are located at distinct points strictly inside the rectangle.

Opposite corners of the room are located at points (0, 0) and (n, m). Walls of the room are parallel to coordinate axes.

At the moment 0, from the point (0, 0) the laser ray is released in the direction of point (1, 1). The ray travels with a speed of  meters per second. Thus, the ray will reach the point (1, 1) in exactly one second after the start.

When the ray meets the wall it‘s reflected by the rule that the angle of incidence is equal to the angle of reflection. If the ray reaches any of the four corners, it immediately stops.

For each sensor you have to determine the first moment of time when the ray will pass through the point where this sensor is located. If the ray will never pass through this point, print  - 1 for such sensors.

Input

The first line of the input contains three integers nm and k (2 ≤ n, m ≤ 100 000, 1 ≤ k ≤ 100 000) — lengths of the room‘s walls and the number of sensors.

Each of the following k lines contains two integers xi and yi (1 ≤ xi ≤ n - 1, 1 ≤ yi ≤ m - 1) — coordinates of the sensors. It‘s guaranteed that no two sensors are located at the same point.

Output

Print k integers. The i-th of them should be equal to the number of seconds when the ray first passes through the point where the i-th sensor is located, or  - 1 if this will never happen.

Examples

input

3 3 41 11 22 12 2

output

1-1-12

input

3 4 61 12 11 22 21 32 3

output

1-1-125-1

input

7 4 51 32 25 15 34 3

output

13295-1

题意是一束光从(0,0)射出,光线速度为根号2的单位每秒,求一路上有k个传感仪,求各个传感仪第一次接收到光线信号的时间,如果接收不到就输出-1。

观察到光线与坐标轴的角度始终为45°,那样的话说明光线的位置可以用一个数字来表示,这个类似八皇后的时候的斜线表示。用两个vector来储存各斜线上的点。用dx,dy可以表示光线方向。
然后就可以枚举光线路径斜线上的传感仪更新答案,再更新光线撞墙的坐标和光线方向,直到光线到达角落。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 2e5 + 10;
vector< pair<int, int> > va[maxn], vb[maxn];
ll ans[maxn];
int main()
{
    int n, m, k;
    memset(ans, 0x3f, sizeof(ans));
    scanf("%d %d %d", &n, &m, &k);
    for(int i = 1; i <= k; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        va[x+y].emplace_back(i, x);
        vb[x-y+m].emplace_back(i, x);
    }

    int x = 0, y = 0; //定义初始坐标
    int dx = 1, dy = 1; //定义初始方向
    ll t = 0; //定义初始时间
    while(true) {
        if(dx == dy) {
            for(auto p:vb[x-y+m]) {
                ans[p.first] = min(ans[p.first], t + abs(p.second - x));
            }
        }
        else {
            for(auto p:va[x+y]) {
                ans[p.first] = min(ans[p.first], t + abs(p.second - x));
            }
        }
        int time = 0x3f3f3f3f;
        if(dx == -1) time = min(time, x);
        else time = min(time, n - x);
        if(dy == -1) time = min(time, y);
        else time = min(time, m - y);
        x = x + time * dx;
        y = y + time * dy;
        t = time + t;
        bool flag1 = (x == 0 || x == n);
        bool flag2 = (y == 0 || y == m);
        if(flag1 && flag2) break;
        if(flag1) dx = -dx;
        if(flag2) dy = -dy;
    }
    for(int i = 1; i <= k; i++) {
        if(ans[i] == 0x3f3f3f3f3f3f3f3f) puts("-1");
        else printf("%I64d\n", ans[i]);
    }
}
				



				
时间: 10-07

Intel Code Challenge Final Round (Div. 1 + Div. 2, Combined) C. Ray Tracing的相关文章

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

C 模拟 题意:给的是一个矩形,然后√2 的速度走,如果走到边上就正常反射,走到角上,暂停反射,我们知道要不循环要不暂停,记录走到的点最短时间 /************************************************************************* > File Name: c.cpp > Author: opas_chenxin > Mail: [email protected] > Created Time: 2016年10月08日

codeforces Intel Code Challenge Final Round (div.1 + div.2 combined)

比赛水掉3题rk559 rating+115 赛后切掉C n年没打cf了终于又重新变蓝了,果然太弱... 1.A题  Checking the Calendar 给定两个星期几,问是否可能分别是两个月的第一天. 水题暴力枚举月份 #include<cstdio> #include<cstring> #include<cstdlib> #include<vector> #include<algorithm> #include<function

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

Description You are given names of two days of the week. Please, determine whether it is possible that during some non-leap year the first day of some month was equal to the first day of the week you are given, while the first day of the next month w

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

传送门:D Dense Subsequence 题意:输入一个m,然后输入一个字符串,从字符串中取出一些字符组成一个串,要求满足:在任意长度为m的区间内都至少有一个字符被取到,找出所有可能性中字典序最小的情况,并按字典序输出 思路:字典序 例如 aaaaaaab < ab  也就是说,如果满足要求的取法中取到了b 那么所有的a都应该被取到,这样才可以保证字典序最小,那么也就是说在26个字母中找到一定要被取的最大字母,然后再确定最大的字母的个数,比它小的全部要取 AC代码: 1 #include

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

链接 题意:输入n,m,表示一个n行m列的矩阵,每一行数字都是1-m,顺序可能是乱的,每一行可以交换任意2个数的位置,并且可以交换任意2列的所有数 问是否可以使每一行严格递增 思路:暴力枚举所有可能的列变换 然后在所有可能的情况下求是否存在一种情况可以使每一行最多进行一次交换最后得到严格递增的矩阵 AC代码: 1 #include "iostream" 2 #include "stdio.h" 3 #include "string.h" 4 us

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

Description You are given a table consisting of n rows and m columns. Numbers in each row form a permutation of integers from 1 to m. You are allowed to pick two elements in one row and swap them, but no more than once for each row. Also, no more tha

模拟。。。 Intel Code Challenge Final Round (Div. 1 + Div. 2, Combined) C

题目大意:给你一个n*m的矩阵,再给你一个小球,从(0,0)以sqrt(2)/s的速度向右上角出发,遇到边框会反弹,遇到角落就直接停止,给你一些点,问小球第一次经过这些点所需要的时间. 思路:模拟一下即可...注意爆int //看看会不会爆int!数组会不会少了一维! //取物问题一定要小心先手胜利的条件 #include <bits/stdc++.h> using namespace std; #define LL long long #define ALL(a) a.begin(), a.

Intel Code Challenge Final Round (Div. 1 + Div. 2, Combined) E - Goods transportation 最大流转最小割转dp

E - Goods transportation 思路:这个最大流-> 最小割->dp好巧妙哦. #include<bits/stdc++.h> #define LL long long #define fi first #define se second #define mk make_pair #define PII pair<int, int> #define PLI pair<LL, int> #define ull unsigned long lo

Intel Code Challenge Final Round (Div. 1 + Div. 2, Combined) G - Xor-matic Number of the Graph 线性基好题

G - Xor-matic Number of the Graph 上一道题的加强版本,对于每个联通块需要按位算贡献. #include<bits/stdc++.h> #define LL long long #define fi first #define se second #define mk make_pair #define PII pair<int, int> #define PLI pair<LL, int> #define ull unsigned lo