Erasing Edges

题目描述

Little Johnny painted on a sheet of paper a polygon with $N$ vertices. Then, for every edge of the polygon, he drew the middle point of the edge. After that, he went to school. When he came back, he found out that his brother had erased the polygon (both the edges and the vertices). The only thing left were the middle points of the edges of the polygon. Help Johnny redraw his polygon.

题意概述

给定一个$N$边形各边的中点，还原这个$N$边形。边可以相交。

数据范围：$3 \le N \le 10000$。

算法分析

设$N$边形第$i$个点的坐标为$(x_i, y_i)$，第$i$条边中点的坐标为$(x_i’, y_i’)$，可以得到以下方程

$$
\left\{
\begin{array}{c}
x_1+x_2=2x_1’ \\
x_2+x_3=2x_2’ \\
\cdots \\
x_N+x_1=2x_N’
\end{array}
\right.
$$

对$y$同理。当$N$为奇数时，方程有唯一解，解出即可；当$N$为偶数时，方程无解或有无数解，只需尝试构造一组解并判断是否合法。

代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

#define random (1.0 * rand() / RAND_MAX)

using namespace std;

static const double EPS = 1e-6;
int cmp(double a, double b) {
  return fabs(a - b) < EPS ? 0 : a < b ? -1 : 1;
}

struct Point {
  double x, y;
  Point(double _x = 0, double _y = 0) : x(_x), y(_y) {}
  Point operator + (const Point &p) const { return Point(x + p.x, y + p.y); }
  Point operator - (const Point &p) const { return Point(x - p.x, y - p.y); }
  Point operator * (const double &n) const { return Point(x * n, y * n); }
  Point operator / (const double &n) const { return *this * (1 / n); }
  Point operator | (const Point &p) const { return *this + (p - *this) * 2; }
};

struct Solver {
private:
  static const int N = 10010;
  int n;
  Point point[N];
  vector <Point> ans;
  void input() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++ i) scanf("%lf%lf", &point[i].x, &point[i].y);
  }
  void process() {
    Point p;
    if (n & 1) {
      double sum = 0;
      for (int i = 1; i <= n; ++ i) sum += point[i].x;
      for (int i = 2; i <= n; i += 2) sum -= point[i].x * 2;
      p.x = sum, sum = 0;
      for (int i = 1; i <= n; ++ i) sum += point[i].y;
      for (int i = 2; i <= n; i += 2) sum -= point[i].y * 2;
      p.y = sum;
    } else p = Point(random * 100000, random * 100000);
    for (int i = 1; i <= n; ++ i) ans.push_back(p), p = p | point[i];
    if (cmp(p.x, ans[0].x) || cmp(p.y, ans[0].y)) printf("NO\n");
    else {
      printf("YES\n");
      for (int i = 0; i < ans.size(); ++ i) printf("%.6lf %.6lf\n", ans[i].x, ans[i].y);
    }
  }

public:
  void solve() { input(), process(); }
} solver;

int main() {
  srand(47), solver.solve();
  return 0;
}