# 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.

## 算法分析

$$\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.$$

## 代码

#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;
}


418 I'm a teapot