arimattiの競プロ精進日記

競プロ問題の解法を記録していきます

ABC197 D - Opposite を解いてみた

問題リンク

atcoder.jp

問題概要

二次元座標平面上に頂点  p _ 0, p _ 1, \cdots, p _ {N-1} からなる正  N 角形がある。頂点  p _ 0, p _ 1, \cdots, p _ {N-1} はこの順に反時計回りに並んでいる。 p _ i の座標を  (x _ i, y _ i) とする。 x _ 0, y _ 0, x _ {\frac{N}{2}}, y _ {\frac{N}{2}} が与えられるので、 x _ 1, y _ 1 を求めよ。

f:id:arimatti:20210607120134p:plain

制約

 4 \leq N \leq 100
 N は偶数

ポイント

  • 正多角形は円にのるため、 x _ 1, y _ 1 は正多角形の中心点を中心として  x _ 0, y _ 0  {\frac{360}{N}} 度回転した座標を求めればよい。
  •  N は偶数のため、正多角形の中心は  x _ 0, y _ 0, x _ {\frac{N}{2}}, y _ {\frac{N}{2}} の中点を取ればよい。
  • 座標回転するために、正多角形の中心を原点に移動する。
  •  (x, y) \theta 回転した座標  (x', y') は以下の式で得られる。

 x' = x cos\theta - y sin\theta
 y' = x sin\theta + y cos\theta

  • 原点に平行移動しているので、回転後の座標を元に戻す。

感想

がっつり幾何問題ですね。やることは平行移動→回転→平行移動と一つ一つの処理はシンプルですが、本番で落ち着いて実装しないとわけわからなくなりそうです。幾何系のライブラリも整理していきたい。

コード

#include <bits/stdc++.h>
#include <atcoder/all>
#define rep(i,n) for (int i = 0; i < (n); i++)
using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int, int>;

const double PI = acos(-1);

struct Point {
  double x, y;
};

Point rotate(Point p, double theta) {
  Point res;
  res.x = p.x * cos(theta) - p.y * sin(theta);
  res.y = p.x * sin(theta) + p.y * cos(theta);
  return res;
}

int main() {
  int n;
  Point p, op;
  cin >> n >> p.x >> p.y >> op.x >> op.y;
  Point center;
  center.x = (p.x+op.x)/2.0;
  center.y = (p.y+op.y)/2.0;
  // 原点移動
  p.x -= center.x;
  p.y -= center.y;
  // x, y を360/n 度回転
  double theta = 2.0 * PI / n;
  Point ans = rotate(p, theta);
  // 原点移動を元に戻す
  ans.x += center.x;
  ans.y += center.y;
  printf("%.10lf %.10lf\n", ans.x, ans.y);
  return 0;
}