読者です 読者をやめる 読者になる 読者になる

水面下の夢

競プロやイラストに興味があります.メインブログがここ.ソシャゲの話はこっち(http://ameblo.jp/0n0-yumechi/).ブログアイコンはYaQ(@8_9_00)さんから.

ARC 042 B - アリの高橋くん

C++ AtCoderARC 競技プログラミング

回答

Submission #468793 - AtCoder Regular Contest 042 | AtCoder

どうやったら現在の点から最短でどこかの辺に向かえるか,という問題として読み取ることができる.
線と直線の距離を求め,一番短い距離のものを出力すればよいのだが…

ここで幾何があまり得意でない私は引っかかった.
どう求めれば良いのか???

参考リンク:
点と直線の距離:点と直線の距離
直線を求める方程式:直線の方程式の求め方[2点(x₁、y₁)と(x₂,y₂)を通る] / 数学II by ふぇるまー |マナペディア|

はい.
はっきり言って高校でやったことを思い出すだけだったのだが,教養のない私は完全に忘れていた.
なので,間違った式を立式してしまい,永久に答えが合わないゲームをしていた.これはひどい

まず直線を二点から求め,それを線と直線の距離公式に当てはめるだけでOKです….
(ちなみに私は変数のミスもやらかしていた.競プロではタイプ数の問題から短い変数名が好まれるが,私はしっかりとした変数名でまずは書いていこうと思う… 本当にくだらないミスだった)

また,出力桁数を調整しないといけない関係で,今回からテンプレートに

cout.precision(10);

を入れることにした.

私の苦悩の結果のプログラムは以下のとおり.

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>
 
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <functional>
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define INF 1<<30
#define MP make_pair
#define mp make_pair
#define pb push_back
#define PB push_back
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define ll long long
#define ull unsigned long long
 
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    int x, y, n;
    cin >> x >> y >> n;
 
    double res = 300.0;
 
    int tx[n], ty[n];
    REP(i, n) {
        cin >> tx[i];
        cin >> ty[i];
    }
 
    REP(i, n) {
        int tx1, ty1, tx2, ty2;
        int cx, cy;
 
        tx1 = tx[i]; ty1 = ty[i];
        if(i < n-1) {
            tx2 = tx[i+1]; ty2 = ty[i+1];
        } else {
            tx2 = tx[0]; ty2 = ty[0];
        }
        cx = x; cy = y;
 
        // y - y1 = ((y2 - y1) / (x2 - x1)) * (x - x1)
        // (y1 - y2) x + (x2 - x1) y - y1 * (x2 - x1) + x1 * (y2 - y1) = 0
        // (y1 - y2) x + (x2 - x1) y - y1 * x2 + x1 * y2= 0
        double a = ty1 - ty2;
        double b = tx2 - tx1;
        double c = -(tx2 * ty1) + tx1 * ty2;
        double cres = fabs(a * cx + b * cy + c) / sqrt(a * a + b * b);
 
        res = min(res, cres);
    }
 
    cout.precision(10);
    cout << res << endl;
    return 0;
}