Codeforces 724C [坐标][乱搞][模拟]

/*
不要低头,不要放弃,不要气馁,不要慌张
题意:
从(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]);
}
}
上一篇:内核中读取UTC时间


下一篇:DOM系列---DOM操作表格