abc289F 题解

某人 vp 时 10min 口胡了这道题，然后调了两天，第一天卡在 WA 4，第二天 WA 7 WA 10 交相辉映，心态快崩了，因此写了这篇题解。

\(a=b\) 处理有借鉴 这篇题解。

first observation：两维独立。

显然。一次操作可以看成两维分别选点操作。后面的操作均在一维上。

second observation：两次分别选择 \(s\) 与 \(t\) 的操作可以看成 \(x \gets x + 2(t - s)\)。

显然。手动模拟都行。

然后你发现一次操作不影响奇偶性，然后可以把两点奇偶性不同的情况判掉。然后你发现你可以移动任意偶数步，就做完了……吗？

判掉 \(s=t\)，那时有可能只会翻转一次。

回到组合两维的地方。我的做法是翻 \(x\) 时永远选择 \(y=c\)。这样子在 \(a \neq b\) 即第一维操作偶数次一定可行。那么 \(a \neq b\) 且 \(c \neq d\) 做完了。接着来看 \(a = b\) 或 \(c = d\)。

现在考虑有至少一者相等。先判掉两维均相等。

如果 \(a = b\) 且 \(sx \neq tx\) 可以先对 \((a, c)\) 操作，\(c = d\) 同理。这样显然不会影响另一维上的操作，因为由构造 \(a \neq b\) 时一定有解。然后做完了。

感觉在空心黄中算是很简单。要不是它难调我觉得空心蓝都行。

#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
vector<int> work(int x, int a, int b, int y) {
  vector<int> w;
  if(a == b) {
    if(x != y) w.push_back(a);
    return w;
  }
  while (x < y) {
    w.push_back(a); w.push_back(a + 1);
    x += 2;
  }
  while(x > y) {
    w.push_back(a+1); w.push_back(a);
    x -= 2;
  }
  return w;
}

vector<pair<int, int> > ans;
int x1, y1, x2, y2, a, b, c, d; 
int solve() {
  ans.clear();
  if(abs(x1 % 2) != abs(x2 % 2)) return 0;
  if(abs(y1 % 2) != abs(y2 % 2)) return 0;
  if(a == b && x1 != x2 && (2 * a - x1) != x2) return 0;
  if(c == d && y1 != y2 && (2 * c - y1) != y2) return 0;
  if(a == b && c == d) {
    if(x1 == x2 && y1 == y2) return 1;
    int x3 = 2 * a - x1, y3 = 2 * c - y1;
    if(x3 == x2 && y3 == y2) return ans.push_back({a, c}), 1;
    else return 0;
  }
  if(a == b && x1 != x2) {
    ans.push_back({a, c}); x1 = 2 * a - x1; y1 = 2 * c - y1;
  }
  if(c == d && y1 != y2) {
    ans.push_back({a, c}); x1 = 2 * a - x1; y1 = 2 * c - y1;
  }
  vector<int> x = work(x1, a, b, x2), y = work(y1, c, d, y2);
  for(auto u : x) ans.push_back({u, c});
  for(auto v : y) ans.push_back({a, v});
  return 1;
}

int main () {
  scanf("%d %d %d %d %d %d %d %d", &x1, &y1, &x2, &y2, &a, &b, &c, &d);
  if(solve()) {
    printf("Yes\n");
    for(auto i : ans) {
      int x = i.first, y = i.second;
      printf("%d %d\n", x, y);
    }
  } else printf("No\n");
}