結果

問題 No.2602 Real Collider
コンテスト
ユーザー InTheBloom
提出日時 2024-01-13 00:13:08
言語 D
(dmd 2.109.1)
結果
WA  
実行時間 -
コード長 11,278 bytes
コンパイル時間 6,517 ms
コンパイル使用メモリ 238,144 KB
実行使用メモリ 12,320 KB
最終ジャッジ日時 2024-09-28 00:33:11
合計ジャッジ時間 11,175 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other WA * 5 RE * 26 TLE * 5 -- * 42
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std;

alias ratio = rational!(BigInt);

void main () {
    // なんか通らないので、有理数でしばく

    int Q = readln.chomp.to!int;
    auto input = readln.split.to!(int[]);
    auto A = tuple(input[0], input[1]);
    auto B = tuple(input[2], input[3]);
    auto C = tuple(input[4], input[5]);

    double r;
    Tuple!(ratio, ratio) center;

    // (i) 三角形を成さない場合 -> 共線条件を用いる
    // (ii) 三角形を成す場合 -> 垂直二等分線の交点を計算する
    if ((B[0]-A[0])*(C[1]-A[1]) == (B[1]-A[1])*(C[0]-A[0])) {
        int M = max(squaredist(A, B), squaredist(A, C), squaredist(B, C));
        r = sqrt(M.to!double)/2;

        if (squaredist(A, B) == M) {
            center = tuple(ratio(A[0]+B[0])/2, ratio(A[1]+B[1])/2);
        }
        else if (squaredist(A, C) == M) {
            center = tuple(ratio(A[0]+C[0])/2, ratio(A[1]+C[1])/2);
        }
        else {
            center = tuple(ratio(C[0]+B[0])/2, ratio(C[1]+B[1])/2);
        }
    }
    else {
        struct line {
            ratio a, b, c;
            // 直線 ax + by = c
        }

        line AB = line(ratio(B[0]-A[0]), ratio(B[1]-A[1]), ratio((B[0]*B[0]-A[0]*A[0])) / 2 + ratio((B[1]*B[1]-A[1]*A[1])) / 2);
        line AC = line(ratio(C[0]-A[0]), ratio(C[1]-A[1]), ratio((C[0]*C[0]-A[0]*A[0])) / 2 + ratio((C[1]*C[1]-A[1]*A[1])) / 2);

        ratio y, x;
        // x, yについて解く(解いた)
        if (AB.b != ratio(0) && AC.b != ratio(0)) {
            y = ((AB.a * AC.c) - (AC.a * AB.c)) / ((AB.a * AC.b) - (AC.a * AB.b));
            x = (AB.c/AB.a) - (AB.b * y);
        }
        else if (AB.b == ratio(0)) {
            x = AB.c * (ratio(1)/AB.a);
            y = (AC.c - (AC.a * x)) / AC.b;
        }
        else {
            x = AC.c * (ratio(1)/AC.a);
            y = (AB.c - (AB.a * x)) / AB.b;
        }

        center = tuple(x, y);
        r = dist(tuple(x.toDecimal(10).to!double, y.toDecimal(10).to!double), tuple(A[0].to!double, A[1].to!double));
    }

    foreach (_; 0..Q) {
        int X, Y; readln.read(X, Y);
        auto dxr = center[0]-X;
        auto dyr = center[1]-Y;

        auto dx = dxr.toDecimal(10).to!double;
        auto dy = dyr.toDecimal(10).to!double;

        if (dy*dy + dx*dx <= r*r) {
            writeln("Yes");
        }
        else {
            writeln("No");
        }
    }
}

T squaredist (T) (Tuple!(T, T) X, Tuple!(T, T) Y) {
    return (X[0]-Y[0])*(X[0]-Y[0]) + (X[1]-Y[1])*(X[1]-Y[1]);
}

double dist (T) (Tuple!(T, T) X, Tuple!(T, T) Y) {
    return sqrt((X[0]-Y[0])*(X[0]-Y[0]) + (X[1]-Y[1])*(X[1]-Y[1]).to!double);
}

void read (T...) (string S, ref T args) {
    auto buf = S.split;
    foreach (i, ref arg; args) {
        arg = buf[i].to!(typeof(arg));
    }
}

/**
___
# 有理数型`rational(T)`

## 特徴
- 実体化が許可されるTは現状`int`/`long`/`std.bigint.BigInt`のみ
- 分母の0は常に許容されない。
- 常に正規形を保つ(分母と分子が互いに素/負数は分子が負/分子が0なら分母は必ず1)
- 演算子'+', '-', '*', '/'及び'=', '+=', '-=', '*=', '/='のオーバーロード
- 比較演算子'==', '!=', '>', '>=', '<', '<='のオーバーロード

## コンストラクタ
- コンストラクタに渡せるのは`std.conv.to`により`T`に変換できるもののみ。
- コンストラクタは`(分子, 分母)`あるいは`(分子)`を受け付ける。

## 演算子オーバーロード
- 各種演算はオーバーフローの可能性があり、それを検出する機構は無いため、十分に注意する必要がある。。
- (代入演算を含む)二項演算の相手が`rational!T`でない場合、次の2つのどちらか片方を満たせば演算が可能
  1. `T`と異なる型`E`を用いて、`rational!E`であり、かつ`std.conv.to`により`E`を`T`に変換可能。
  2. `std.conv.to`により`T`に変換可能な型であって、`this (E) (E num)`コンストラクタにより`rational!T`に変換可能。

## 小数近似
- `toDecimal()`を呼び出すと、分子と分母を`std.conv.to`により`real`に変換した値を用いて小数近似した結果を返す。
___
 */

import std.bigint;
struct rational (T)
if (
    is (T == int) ||
    is (T == long) ||
    is (T == std.bigint.BigInt)
    )
{
    // Depends on
    import std.exception : enforce;
    import std.format : format;
    import std.conv : to;

    T numerator;
    T denominator = 1.to!(T);

    /* -- constructors -- */
    this (E1, E2) (E1 num, E2 deno, int place = __LINE__)
    if (__traits(compiles, (num.to!(T))) && __traits(compiles, (deno.to!(T))))
    in {
        enforce(deno != 0, format("Line %s : Denominator must not equal to zero.", place));
    }
    do {
        numerator = num.to!(T), denominator = deno.to!(T);
        normalization();
    }

    this (E) (E num)
    if (__traits(compiles, (num.to!(T))))
    {
        numerator = num.to!(T), denominator = 1.to!(T);
        normalization();
    }

    /* -- invariant -- */
    invariant {
        enforce(denominator != 0, format("In struct rational!(%s) : zero division occured.", T.stringof));
    }

    /* -- methods -- */
    void normalization () {
        /* std.bigint.BigIntで-0とかいう謎の数が生成される可能性があるので、判定をこうしてる */
        if (-1 < numerator && numerator < 1) { numerator = 0; denominator = 1; return; }

        /* 互いに素にする */
        auto GCD = this.rational_gcd(numerator, denominator);
        if (1 < GCD) {
            numerator /= GCD; denominator /= GCD;
        }

        /* 符号正規化 */
        if (denominator < 0) {
            numerator *= -1; denominator *= -1;
        }
    }

    /** -- opUnary -- **/
    auto opUnary (string op : "+") ()
    {
        return this;
    }

    auto opUnary (string op : "-") ()
    {
        numerator *= -1;
        return this;
    }

    /** -- opBinary -- **/
    auto opBinary (string op : "+") (rational!T rhs)
    {
        /* (a/b) + (c/d) = (ad+bc)/bd */
        /* boost/rationalの計算を参考にした。
           (https://github.com/boostorg/rational/blob/develop/include/boost/rational.hpp) */
        auto g = this.rational_gcd(this.denominator, rhs.denominator);

        auto b1 = this.denominator / g;
        auto d1 = rhs.denominator / g;

        auto res = rational!T(0);
        res.numerator = (this.numerator * d1) + (rhs.numerator * b1);
        res.denominator = b1 * d1 * g;

        auto div = this.rational_gcd(res.numerator, g);
        res.numerator /= g, res.denominator /= g;
        return res;
    }

    auto opBinary (string op : "-") (rational!T rhs)
    {
        /* (a/b) - (c/d) = (a/b) + ((-c)/b) */
        return opBinary!"+"(-rhs);
    }

    auto opBinary (string op : "*") (rational!T rhs)
    {
        /* (a/b) * (c/d) = ((a*c)/(b*d)) */
        T num = this.numerator;
        T den = this.denominator;

        // GCD1 = gcd(a, d), GCD2 = gcd(b, c)
        auto GCD1 = this.rational_gcd(num, rhs.denominator);
        auto GCD2 = this.rational_gcd(den, rhs.numerator);

        num /= GCD1;
        den /= GCD2;

        num *= rhs.numerator / GCD2; den *= rhs.denominator / GCD1;

        auto res = rational!T(0);
        res.numerator = num, res.denominator = den;

        return res;
    }

    auto opBinary (string op : "/") (rational!T rhs)
    in {
        assert(rhs != rational!T(0), "Zero division.");
    }
    do {
        /* (a/b) / (c/d) = (a/b) * (d/c) */
        auto res = rational!T(0);
        res.numerator = rhs.denominator, res.denominator = rhs.numerator;
        return opBinary!"*"(res);
    }

    // いろんな型に対応させる。
    auto opBinary (string op, E) (E rhs)
    if ((op == "+" || op == "-" || op == "*" || op == "/") &&
        __traits(compiles, rational!(T)(rhs)))
    {
        auto ret = rational!(T)(rhs);
        return opBinary!(op)(ret);
    }

    /** -- opBinaryRight -- **/
    auto opBinaryRight (string op, E) (E lhs)
    if ((op == "+" || op == "-" || op == "*") &&
        __traits(compiles, rational!(T)(lhs)))
    {
        auto ret = rational!(T)(lhs);
        return opBinary!(op)(ret);
    }

    auto opBinaryRight (string op, E) (E lhs)
    if ((op == "/") &&
        __traits(compiles, rational!(T)(lhs)))
    {
        auto ret = rational!(T)(lhs);
        return opBinary!("*")(rational!T(ret.deno, ret.num));
    }

    /** -- opAssign -- **/
    void opAssign (rational!T rhs) {
        numerator = rhs.numerator;
        denominator = rhs.denominator;
    }

    void opAssign (E) (E rhs)
    if (__traits(compiles, rhs.to!(T)))
    {
        numerator = rhs.to!(T);
        denominator = 1.to!(T);
        normalization();
    }

    /** -- opOpAssign -- **/
    void opOpAssign (string op : "+") (rational!T rhs)
    {
        auto g = this.rational_gcd(rhs.denominator, this.denominator);
        this.denominator /= g;
        this.numerator = this.numerator * (rhs.denominator / g) + rhs.numerator * this.denominator;
        g = this.rational_gcd(this.numerator, g);
        this.numerator /= g;
        this.denominator *= rhs.denominator/g;
    }

    void opOpAssign (string op : "-") (rational!T rhs)
    {
        rhs.numerator *= -1;
        opOpAssign!"+"(rhs);
    }

    void opOpAssign (string op : "*") (rational!T rhs)
    {
        auto GCD1 = this.rational_gcd(numerator, rhs.denominator);
        auto GCD2 = this.rational_gcd(denominator, rhs.numerator);

        numerator /= GCD1; denominator /= GCD2;

        numerator *= rhs.numerator / GCD2;
        denominator *= rhs.denominator / GCD1;
    }

    void opOpAssign (string op : "/") (rational!T rhs)
    {
        opOpAssign!"*"(rational!T(rhs.denominator, rhs.numerator));
    }

    // いろんな型に対応させる。
    void opOpAssign (string op, E) (E rhs)
    if ((op == "+" || op == "-" || op == "*" || op == "/") &&
            __traits(compiles, rational!(T)(rhs)))
    {
        auto ret = rational!(T)(rhs);
        opOpAssign!(op)(ret);
    }

    string toString () {
        return format("%s/%s", numerator, denominator);
    }

    /** -- opEqual -- **/
    bool opEqual (rational!T rhs) {
        return this.numerator == rhs.numerator && this.denominator == rhs.denominator;
    }

    /** -- opCmp -- **/
    int opCmp (rational!T rhs) {
        /* (a/b) < (c/d) := ad < bc */
        T left = this.numerator * rhs.denominator;
        T right = this.denominator * rhs.numerator;
        if (left < right) return -1;
        if (right < left) return 1;
        return 0;
    }

    string toDecimal (size_t digits = 10) {
        string res;
        auto num = numerator;
        auto den = denominator;
        bool minus = false;

        if (num < 0) {
            num = -num;
            minus = true;
        }

        foreach (i; 0..digits) {
            res ~= (num/den).to!string;
            if (i == 0) res ~= '.';
            num %= den;
            num *= 10;
        }
        if (minus) res = "-" ~ res;
        return res;
    }

    T rational_gcd (T x, T y) {
        T tmp;
        while (y != 0) {
            tmp = y;
            y = x % y;
            x = tmp;
        }
        return x;
    }
}
0