标签：模拟
Wherever the destination is, whoever wemeet, let's render this song together.
On a Cartesian coordinate plane lies arectangular stage of sizew × h, represented by a rectangle withcorners (0, 0), (w, 0), (w, h) and (0, h).
On the sides of the stage standndancers. The i-th of them falls into one of the following groups:
- Vertical: stands at (xi, 0), moves in positivey direction (upwards);
- Horizontal: stands at (0, yi), moves in positivex direction (rightwards).
According to choreography, thei-thdancer should stand still for the first ti milliseconds, andthen start moving in the specified direction at 1 unit per millisecond, untilanother border is reached. It is guaranteed that no two dancers have the samegroup, position and waiting time at the same time.
When two dancers collide (i.e. are on thesame point at some time when both of them are moving), they immediatelyexchange their moving directions and go on.
Dancers stop when a border of the stage isreached. Find out every dancer's stopping position.
Input
The first line of input contains threespace-separated positive integersn, w and h (1 ≤ n ≤ 100 000, 2 ≤ w, h ≤ 100 000) — the number of dancers and the width and height of the stage,respectively.
The following n lines each describesa dancer: thei-th among them contains three space-separated integers gi,pi, andti (1 ≤ gi ≤ 2, 1 ≤ pi ≤ 99 999, 0 ≤ ti ≤ 100 000), describing a dancer's groupgi(gi = 1 — vertical, gi = 2 — horizontal), position, and waitingtime. Ifgi = 1 then pi = xi; otherwisepi = yi. It's guaranteed that 1 ≤ xi ≤ w - 1 and 1 ≤ yi ≤ h - 1. It is guaranteed that no two dancershave the same group, position and waiting time at the same time.
Output
Output n lines, thei-th ofwhich contains two space-separated integers (xi, yi) — the stopping positionof thei-th dancer in the input.
Example
Input
8 10 8
1 1 10
1 4 13
1 7 1
1 8 2
2 2 0
2 5 14
2 6 0
2 6 1
Output
4 8
10 5
8 8
10 6
10 2
1 8
7 8
10 6
Input
3 2 3
1 1 2
2 1 1
1 1 5
Output
1 3
2 1
1 3
Note
The first example corresponds to theinitial setup in the legend, and the tracks of dancers are marked withdifferent colours in the following figure.
In the second example, no dancers collide.
题意：有许多舞者位于舞台边界，她们会在指定的等待时间过后上场，初始朝着固定的方向走向终点，行进速度相同，在舞台上若两人发生碰撞（即同一时间点重合），那么两人各自交换方向，问最终各个舞者的终点
分析：两人相撞的过程实际上就是互相交换，总体来说对她们的终点位置不发生影响，影响的是两人的终点对应关系，和一道入门题（蚂蚁过独木桥）蛮像的
两人相撞的条件是：（初始位置-等待时间）相等
相撞后的对应终点匹配关系可以通过排序来解决，具体有严谨的数学证明，然而本蒟蒻不会证，官方的题解也是看得一知半解，总觉得怪怪的，但还好AC了
参考代码
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int n,w,h;
const int maxt=100005,maxn=250000,maxw=200005;
int g[maxn],p[maxn],t[maxn],x[maxn];
pair<int,int>ans[maxn];
vector<int>vx[maxn],vy[maxn];
bool cmp(int x,int y)
{
return p[x]<p[y];
}
int main()
{
n=read(),w=read(),h=read();
for(int i=1;i<=n;i++)
{
g[i]=read(),p[i]=read(),t[i]=read();
x[i]=p[i]-t[i]+1e5;
if(g[i]==1)vx[x[i]].push_back(i);
else vy[x[i]].push_back(i);
}
for(int i=1;i<=2e5;i++)
{
int lx=vx[i].size();
int ly=vy[i].size();
sort(vx[i].begin(),vx[i].end(),cmp);
sort(vy[i].begin(),vy[i].end(),cmp);
for(int j=0;j<lx;j++)
{
int id=vx[i][j];
int right=lx-j;
if(right>ly)ans[id]=make_pair(p[vx[i][j+ly]],h);
else ans[id]=make_pair(w,p[vy[i][right-1]]);
}
for(int j=0;j<ly;j++)
{
int id=vy[i][j];
int up=ly-j;
if(up>lx)ans[id]=make_pair(w,p[vy[i][j+lx]]);
else ans[id]=make_pair(p[vx[i][up-1]],h);
}
}
for(int i=1;i<=n;i++)printf("%d %d\n",ans[i].first,ans[i].second);
return 0;
}
