/*
不要低头,不要放弃,不要气馁,不要慌张
题意:
从(0,0)出发与x轴正方向呈45度角的射线,在给定的矩形区域内不断发射,直到射入矩形的某个角停止。
给出多个坐标,问光线最早经过某坐标的时间。
思路:
1.明确光线反射次数不会超过n+m次(好像是这样==没细想)
2.发现规律,光线要么是符合x+y=k,或者x-y=k的直线。而且每次反射都会变到不同类型的直线。
3.知道出发点,算出反射点。
4.把点放到直线的vector里边。每次到了某条直线把直线上的点扫一遍,然后删掉。 */ #include<bits/stdc++.h>
using namespace std;
struct point{
point(){}
point(long long xx,long long yy,int iid){
x=xx;y=yy;id=iid;
}
long long x,y,id;
};
bool operator <(const point &a,const point &b){
if(a.x!=b.x)return a.y<b.y;
return a.x<b.x;
}
set<point> ms1[],ms2[];
long long rel[];
int n,m,k;
point next(point a,int num){
if(num&){
long long w=a.x+a.y;
long long x=;
long long y=w-x;
if(y>=&&y<=m&&(x!=a.x||y!=a.y))return point(x,y,);
x=n;
y=w-x;
if(y>=&&y<=m&&(x!=a.x||y!=a.y))return point(x,y,);
y=;
x=w-y;
if(x>=&&x<=n&&(x!=a.x||y!=a.y))return point(x,y,);
y=m;
x=w-y;
if(x>=&&x<=n&&(x!=a.x||y!=a.y))return point(x,y,);
}
else{
long long w=a.x-a.y;
long long x=;
long long y=x-w;
if(y>=&&y<=m&&(x!=a.x||y!=a.y))return point(x,y,);
x=n;
y=x-w;
if(y>=&&y<=m&&(x!=a.x||y!=a.y))return point(x,y,);
y=;
x=y+w;
if(x>=&&x<=n&&(x!=a.x||y!=a.y))return point(x,y,);
y=m;
x=y+w;
if(x>=&&x<=n&&(x!=a.x||y!=a.y))return point(x,y,);
}
}
long long cal(point a,point b){
return max(a.x-b.x,b.x-a.x);
}
int main()
{
memset(rel,-,sizeof(rel));
long long x,y,bf=;
scanf("%d%d%d",&n,&m,&k);
for(int i=;i<=k;i++){
scanf("%lld%lld",&x,&y);
ms1[x-y+].insert(point(x,y,i));
ms2[x+y].insert(point(x,y,i));
}
point st(,,);
int num=;
while(){
x=st.x;y=st.y;
if(num&){
while(!ms2[x+y].empty()){
long long xx=ms2[x+y].begin()->x;
long long yy=ms2[x+y].begin()->y;
int id=ms2[x+y].begin()->id;
if(rel[id]==-)
rel[id]=bf+cal(point(xx,yy,),st);
ms1[x-y+].erase(point(xx,yy,));
ms2[x+y].erase(point(xx,yy,));
}
}
else{
while(!ms1[x-y+].empty()){
long long xx=ms1[x-y+].begin()->x;
long long yy=ms1[x-y+].begin()->y;
int id=ms1[x-y+].begin()->id;
if(rel[id]==-)
rel[id]=bf+cal(point(xx,yy,),st);
ms1[x-y+].erase(point(xx,yy,));
ms2[x+y].erase(point(xx,yy,));
}
}
bf+=cal(st,next(st,num));
st=next(st,num);
num++;
if((st.x==&&st.y==)||(st.x==&&st.y==m)||(st.x==n&&st.y==)||(st.x==n&&st.y==m))break;
}
for(int i=;i<=k;i++){
printf("%lld\n",rel[i]);
}
}

最新文章

  1. Transaction事务传播行为种类PROPAGATION_REQUIRED
  2. IntelliJ IDEA常用设置及快捷键
  3. Ubuntu 下误修改用户组导致sudo命令无效
  4. String,StringBuffer,StringBuilder三者区别
  5. MVC form post 传值
  6. 【转】Android API 中文(14) —— ViewStub
  7. Hot-Bar 軟板設計注意事項
  8. 第二章:1.0 Django 入门和开发环境
  9. Centos环境下搭建Asp.NET Core环境和安装Jexus
  10. 基于Webpack, KnockoutJs,esyui,koeasyui实现类vue-cli生成的模板框架
  11. 动态规划——Dungeon Game
  12. go语言入门教程:基本语法之数据类型
  13. Python排序算法——选择排序
  14. HDU 1171 01背包
  15. Android 浅谈 设计与屏幕适配 【1.6235449734285716】
  16. 二级联动的作业&amp;左右移动作业
  17. spring案列——annotation配置
  18. 【Head First Servlets and JSP】笔记 28: 过滤器与包装器
  19. 洛谷P3616 富金森林公园
  20. Moodle插件开发——Blocks(版块)

热门文章

  1. 苹果IOS系统SVN命令 同样适用于linux系统
  2. Linux摄像头驱动学习之:(五)UVC-分析设备描述符
  3. O365 &quot;打开或关闭脚本&quot;功能
  4. linux后台运行和关闭、查看后台任务(转)
  5. 新策略构思 dual thrust
  6. IOS 使用FMDB多线程访问数据库 及databaseislocked的问题
  7. hybrid app 简介
  8. ubuntu15.10跑裸机程序跑.bin文件
  9. union all 取代 select中的case when 提高查询效率
  10. CF 600B Queries about less or equal elements --- 二分查找