CF46G-Emperor's-Problem

CodeForces的标签中说这题是计算几何题，，，而官方题解里说这是贪心题，，，然而我认为这就是一道暴力题。。

设有两个点$(x_1,y_1)$和$(x_2,y_2)$，则这条边的长$l=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$，那么$l^2=(x_1-x_2)^2+(y_1-y_2)^2$。我们定义{X,Y}为这条边的移动量，则$\{X,Y\}=\{x_1-x_2,y_1-y_2\}$。所以有$X^2+Y^2=l^2$。

假设有一个n边形，则有$\{\sum_{i=1}^{i=n}X_i,\sum_{i=1}^{i=n}Y_i\}=\{0,0\}$，所以$\sum_{i=1}^{i=n}(X_i)^2$和$\sum_{i=1}^{i=n}(Y_i)^2$皆为偶数，所以$\sum_{i=1}^{i=n}(l_i)^2$为偶数。

于是我们可以假设有一点为(0,0),第一条边为最长边。从4开始穷举$l^2$(因为1,2,3是不可能作为$l^2$)，我们知道从(0,0)为一个端点，选另一个整数格点作为另一个端点且线段长度为l的线段最多有8个，我们可以任意选一个线段作为第一条边，于是$X_1$和$Y_1$便就已知了。然后就转化为了一个更简单的问题：已知$X_1$和$Y_1$的值，求$\left\{\begin{matrix} \sum_{i=2}^{i=n}X_i=-X_1 \ \sum_{i=2}^{i=n}Y_i=-Y_1 \ l_{i(2\le i\le n)}\le l_1 \end{matrix}\right.$的一组解。这个可以配合奇偶性快速求出。

代码如下：

#include <bits/stdc++.h>
using namespace std;

struct point {
  int x, y, r;
  point() {}
  point(int a, int b) : x(a), y(b), r(a * a + b * b) {}
  bool operator==(point &cmp) const { return r == cmp.r; }
};
vector<point> vec;
vector<pair<int, int>> X, Y;

bool cmp1(const point &a, const point &b) { return a.r < b.r; }
bool cmp2(const point &a, const point &b) {
  return atan2(a.y + 0.0, a.x + 0.0) < atan2(b.y + 0.0, b.x + 0.0) - 1e-8;
}
void init() {
  for (int i = 0; i < 200; i++) {
    for (int j = i; j < 200; j++) {
      vec.push_back(point(i, j));
    }
  }
  sort(vec.begin(), vec.end(), cmp1);
  vec.erase(unique(vec.begin(), vec.end()), vec.end());
}

int main() {
  ios_base::sync_with_stdio(false);
  init();
  int n;
  cin >> n;
  int del = 0;
  for (int i = 4, cnt = 2, bit = 1;; i++) {
    int p = bit;
    int q = (vec[i].x + vec[i].y) & 1;
    if (p && q) {
      if (++cnt == n)
        del = 3;
      ++cnt;
    } else if (p && !q) {
      if (++cnt == n)
        del = 6;
    } else if (!p && !q)
      ++cnt;
    bit = (p + q) & 1;
    if (cnt >= n) {
      int sum = 0;
      for (int j = 1; j <= i; j++) {
        if (j == del)
          continue;
        X.push_back(make_pair(vec[j].x, X.size()));
        Y.push_back(make_pair(vec[j].y, Y.size()));
        sum = (sum + vec[j].x) & 1;
      }
      if (sum & 1)
        swap(X[0].first, Y[0].first);
      break;
    }
  }
  sort(X.begin(), X.end());
  sort(Y.begin(), Y.end());
  int sumX = 0, sumY = 0;
  for (int i = X.size() - 1; i >= 0; i--) {
    if (abs(sumX - X[i].first) < abs(sumX + X[i].first)) {
      sumX -= X[i].first;
      X[i].first = -X[i].first;
    } else
      sumX += X[i].first;
    if (abs(sumY - Y[i].first) < abs(sumY + Y[i].first)) {
      sumY -= Y[i].first;
      Y[i].first = -Y[i].first;
    } else
      sumY += Y[i].first;
  }
  while (sumX || sumY)
    ;
  for (int i = 0; i < X.size(); i++) {
    vec[X[i].second].x = X[i].first;
    vec[Y[i].second].y = Y[i].first;
  }
  vec.erase(vec.begin() + X.size(), vec.end());
  sort(vec.begin(), vec.end(), cmp2);
  cout << "YES" << endl;
  int sumx = 0, sumy = 0;
  for (int i = 0; i < vec.size(); i++) {
    sumx += vec[i].x;
    sumy += vec[i].y;
    cout << sumx << ' ' << sumy << endl;
  }
  return 0;
}