数学题,但可以贪心过

题意:

在平面直角坐标系中,给定起点$S(sx,sy)$与终点$T(tx,ty)$,和一个长方形$R := {(x,y)|a-0.5\le x \le b+0.5,c-0.5\le y \le d+0.5}$,S上有一颗棋子。每次操作可以在长方形中选定一个点,让棋子跳到指定点的对称点,也就是在长方形内$选定点(sx,sy),使棋子从(x,y)跳到(2sx-x,2sy-y)$,问能不能在$10^6$次操作内使得棋子到达T,如果能到达,输出每次操作选定的点。
注意,输出不要求操作数最少。

做法:

分开考虑纵坐标与横坐标。

对于横坐标,考虑到当$b-a\ge1$时,连续选择$(a,c)$点与$(a+1,c)$可使得棋子从$(x,y)$跳到$(x\pm2,y)$的位置,
因此可以重复至多$2\times 10^5$次使得棋子的横坐标与T相同。
对于$a\=b$的情况,特判处理。
纵坐标同理。
总操作次数上限为$4\times10^5$,没问题。

注意:

每次操作后,x坐标和y坐标的奇偶性不变。因此要特判处理。

#include <bits/stdc++.h>
#define int long long

using namespace std;

inline int read()
{
    int s=0;
    scanf("%lld",s);
    return s;
}
int sx,sy,tx,ty,a,b,c,d,cnt;
struct ans{
    int x,y;
}ans[1000010];
void move(int x,int y){
    sx=2*x-sx;
    sy=2*y-sy;
    ans[cnt++]={x,y};
}
signed main()
{
    //ios::sync_with_stdio(false);
    sx=read(),sy=read(),tx=read(),ty=read();
    a=read(),b=read(),c=read(),d=read();
    if(sx==tx&&sy==ty) puts("Yes"),exit(0);
    int lenx=b-a,leny=d-c;
    if(sx%2!=tx%2) puts("No"),exit(0);
    if(sy%2!=ty%2) puts("No"),exit(0);
    if(lenx==0&&sx!=tx) move(a,c);
    if(leny==0&&sy!=ty) move(a,c);
    if(lenx==0){
        if(sx!=tx) puts("No"),exit(0);
    }
    else{
        while(sx<tx){
            move(a,c);
            move(a+1,c);
        }
        while(sx>tx){
            move(a+1,c);
            move(a,c);
        }
    }
    if(leny==0){
        if(sy!=ty) puts("No"),exit(0);
    }
    else{
        while(sy<ty){
            move(a,c);
            move(a,c+1);
        }
        while(sy>ty){
            move(a,c+1);
            move(a,c);
        }
    }
    puts("Yes");
    for(int i=0;i<cnt;i++){
        cout<<ans[i].x<<" "<<ans[i].y<<"\n";
    }
    return 0;
}

作者 kangliyang

发表回复