ABC168 C - : (Colon) をベクトル計算で解く

ABC168のC問題ではゴリゴリの幾何問題が出題され，「余弦定理」がツイッターでトレンド入りするなど話題になりました。

私は普通に余弦定理を用いて解いたのですが，結構いろいろな解き方があったようです。ここでは，自分が後で思いついたうちの１つである「ベクトル」を用いた解法を示していきたいと思います（ベクトルの内積の定義に ${\rm cos}$ が使われているので，本質的には余弦定理と同じですが）。

問題はこちら atcoder.jp

前提

時計の中心を $O$ とし，時針，分針の $O$ でない端点をそれぞれ $A,B$ と表す。また， $|OA|=a,|OB|=b$ とし（長さが大文字なのは気持ち悪かったので問題文から変更しています）， $x$ 軸の正の方向と $OA,OB$ とのなす角をそれぞれ $\theta,\varphi$ と置く。以下角度は弧度法で表す。

解法

$A,B$ の初期位置を $A\,(a,0),\ B\,(b,0)$ とし，時針，分針が反時計回りに動くとして一般性を失わない。

$OA$ は $12$ 時間（ $720$ 分）に $2 \pi$ ， $OB$ は $1$ 時間（ $60$ 分）に $2 \pi$ 回転するから，

$H$ 時 $M$ 分においては $\theta = (60H+M)\pi / 360,\ \varphi = (60H+M)\pi / 30$ であり， $\overrightarrow{OA}=(a\, {\rm cos} \theta,\ a\, {\rm sin} \theta),\ \overrightarrow{OB}=(b\, {\rm cos} \varphi,\ b \, {\rm sin} \varphi)$ 。

ここで，求める長さは $|\overrightarrow{AB}|$ 。

$|\overrightarrow{AB}|^2 = |\overrightarrow{OB}-\overrightarrow{OA}|^2 = a^{2} + b^{2} - 2\overrightarrow{OA} \cdot \overrightarrow{OB}$

これを計算して平方根をとれば，答えが出ます。

STLには内積を求めるinner_product関数がありますが，int型の計算しかできないようだったので（よく調べてないけど），double型で内積を求める関数を作ってみました。

コード

#include <bits/stdc++.h>
using namespace std;
const double pi=acos(-1);
double Naiseki(vector<double> x,vector<double> y);

int main(){
    double a,b,h,m;
    cin>>a>>b>>h>>m;

    vector<double> A={a,0};
    vector<double> B={b,0};

    double time=60*h+m;

    double theta=pi*time/360;
    double phi=pi*time/30;

    A={a*cos(theta),a*sin(theta)};
    B={b*cos(phi),b*sin(phi)};

    cout<<setprecision(10);
    cout<<sqrt(a*a+b*b-2*Naiseki(A,B))<<endl;
}

double Naiseki(vector<double> x,vector<double> y){
    double ip=0;
    for(int i=0; i<x.size(); i++){
        ip+=x[i]*y[i];
    }
    return ip;
}

頭良くなりたい人

文系大学生shadeのブログです。競技プログラミングや人文学の話題，受験ネタなど。

ABC168 C - : (Colon) をベクトル計算で解く

前提

解法

コード