ABC197 D 解答

D - Opposite (831)

問題文

x 軸の正の向きを右、y 軸の正の向きを上とする 2 次元座標平面上に、p_0, p_1, p_2, … , p_(N-1)の N 個の頂点からなる正 N 角形があります。
ここで N は偶数であることが保証され、頂点 p_0, p_1, p_2, … , p_(N-1) はこの順に反時計回りに並んでいます。p_i の座標を(x_i, y_i) とします。x_0, y_0, x_(N/2), y_(N/2)が与えられるので、x_1, y_1 を求めてください。

制約

4 ≤ N ≤100
N は偶数
0 ≤ x_0, y_0 ≤100
0 ≤ x_(N/2), y_(N/2) ≤ 100
(x_0, y_0) ≠ (x_(N/2), y_(N/2))
入力に含まれる値は全て整数である

考察

数学の問題ですね。複素数を使うなど色々と考え方はありますが、今回は高校範囲の三角関数を使った回転行列で解いてみようと思います（今って複素数も高校生でやるようになったんですかね）。

ちょっと試しに原点中心の6角形を描いてみましょう。

次にこれに外接円とおまけを付け加えましょう。

間の角度をθとすると、この問題は、

ある座標（x_0,y_0）を円の中心からθだけ回転させた座標を求めよ

という問題になります。

次に行列の回転を加法定理から導いてみます（調べればでてきますので、わかっている方は先に進みください）。

さいたこすもすこすもすさいた

ってやつです。

次の図を考えます。

まず、三角関数を使えば次の関係がわかります。

x_0 = r cos α
y_0 = r sin α
x_1 = r cos (α＋β)
y_1 = r sin (α＋β)

x_1とy_1を加法定理を使って変形します

x_1 = r cos (α+β) = r (cos α cos β - sin α sin β)
y_1 = r sin (α+β) = r (sin α cos β + cos α sin β)

x_0 = r cos α, y_0 = r sin α をつかってもう少し変形します。

x_1 = x_0 cos β - y_0 sin β
y_1 = y_0 cos β + x_0 sin β

これでβだけ回転する場合の変換ができました。これを行列で表現しますと

cos β  -sin β
sin β  cos β

というよく見る形になるわけですね。

これで説明はおしまいです。最後に流れをまとめます。

１．中心座標を求める。（2点の座標の平均）
２．中心が原点に来るように平行移動する
３．回転角を求める。（2π/N [rad]）
４．上式を使って回転させる。
５．平行移動した分を元に戻す。

回転角は円の一周が360[度]、2π[rad]ですので、それを N 等分することにより１つ当たりの角度を算出しています。

実装

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

int main()
{
   int n;
   double x0,y0,x2,y2;
   cin >> n >> x0 >> y0 >> x2 >> y2;

   double mx,my;
   mx = (x0+x2)/2;
   my = (y0+y2)/2;

   x0 -= mx;
   y0 -= my;


   double theta = 2*M_PI / n;
   double s,c;
   s = sin(theta);
   c = cos(theta);
   double ansx,ansy;
   ansx = x0 * c - y0 * s + mx;
   ansy = x0 * s + y0 * c + my;
   printf("%.6f %.6f\n",ansx,ansy);
   return 0;
}

あとがき

[rad]と[度]を変換する時に私はよく比の式を使います。比の式を立てて、外側と内側で掛け算するやつです。

2*π [rad] : 360 [度] = θ [rad] : X [度]
360 * θ = 2*π * X
θ = 2*π * X / 360

これ高校の化学の先生がよく使っていたのですがなかなか便利です。困ったら使いってみてはいかがでしょうか。