結果

問題 No.2628 Shrinkage
コンテスト
ユーザー tobisatis
提出日時 2024-02-16 23:56:23
言語 C#
(.NET 8.0.404)
結果
AC  
実行時間 59 ms / 2,000 ms
コード長 8,944 bytes
コンパイル時間 8,064 ms
コンパイル使用メモリ 167,324 KB
実行使用メモリ 192,964 KB
最終ジャッジ日時 2024-09-28 23:08:49
合計ジャッジ時間 10,624 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 28
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (92 ms)。
MSBuild のバージョン 17.9.6+a4ecab324 (.NET)
  main -> /home/judge/data/code/bin/Release/net8.0/main.dll
  main -> /home/judge/data/code/bin/Release/net8.0/publish/

ソースコード

diff # 

namespace AtCoder;

#nullable enable

using System.Numerics;

using G = Geometry2D<Rational<long>, RationalComplex>;

readonly record struct RationalComplex(Rational<long> X, Rational<long> Y) : IComplexWrapper<RationalComplex, Rational<long>>
{
    public static implicit operator RationalComplex((Rational<long>, Rational<long>) value) => new(value.Item1, value.Item2);
    public static implicit operator (Rational<long>, Rational<long>)(RationalComplex self) => (self.X, self.Y);
    public static RationalComplex Factory(Rational<long> x, Rational<long> y) => new(x, y);
    public static Rational<long> SqrtValue(Rational<long> value) => throw new NotImplementedException();
    public static int Sign(Rational<long> value) => value.CompareTo(0);
}

interface IComplexWrapper<TSelf, TElement> where TSelf : IComplexWrapper<TSelf, TElement>
{
    TElement X { get; }
    TElement Y { get; }
    static abstract TSelf Factory(TElement x, TElement y);
    static abstract TElement SqrtValue(TElement value);
    static abstract int Sign(TElement value);
}

static partial class Geometry2D<T, C>
    where T :
        IComparable<T>,
        IEqualityOperators<T, T, bool>,
        IComparisonOperators<T, T, bool>,
        IAdditionOperators<T, T, T>,
        ISubtractionOperators<T, T, T>,
        IMultiplyOperators<T, T, T>,
        IDivisionOperators<T, T, T>,
        IAdditiveIdentity<T, T>,
        IMultiplicativeIdentity<T, T>
    where C : struct, IComplexWrapper<C, T>
{
    public static T DotProduct(C l, C r) => l.X * r.X + l.Y * r.Y;
    public static T CrossProduct(C l, C r) => l.X * r.Y - l.Y * r.X;
    public static T Magnitude2(C e) => e.X * e.X + e.Y * e.Y;
    public static T Magnitude(C e) => C.SqrtValue(Magnitude2(e));
    public static C Add(C l, C r) => C.Factory(l.X + r.X, l.Y + r.Y);
    public static C Sub(C l, C r) => C.Factory(l.X - r.X, l.Y - r.Y);
    public static C Mul(C l, C r) => C.Factory(l.X * r.X - l.Y * r.Y, l.X * r.Y + l.Y * r.X);
    public static C MulConst(C e, T k) => C.Factory(e.X * k, e.Y * k);
    public static C DivConst(C e, T k) => C.Factory(e.X / k, e.Y / k);
    public static bool Equal(C l, C r) => l.X == r.X && l.Y == r.Y;
    public static C Unit(C e) => DivConst(e, Magnitude(e));

    public record struct DirectedSegment(C Ab, C Ad, bool Ends)
    {
        public readonly C Vector => Sub(Ad, Ab);
    }

    public static int CounterClockwise(DirectedSegment ds, C target)
    {
        var v = Sub(target, ds.Ab);
        var crossProduct = C.Sign(CrossProduct(ds.Vector, v));
        if (crossProduct == 0)
        {
            if (!ds.Ends) return 0;
            if (C.Sign(DotProduct(ds.Vector, v)) < 0) return -1; // other side
            if (C.Sign(DotProduct(v, v) - DotProduct(ds.Vector, ds.Vector)) > 0) return 1;
            return 0; // on the segment
        }
        return crossProduct > 0 ? 2 : -2;
    }

    public static C? Intersection(DirectedSegment ds1, DirectedSegment ds2)
    {
        var (v1, v2, v3) = (ds1.Vector, ds2.Vector, Sub(ds2.Ab, ds1.Ab));
        var k = CrossProduct(v1, v2);
        if (k == T.AdditiveIdentity) return null;
        var s = CrossProduct(v3, v2) / k;
        var t = CrossProduct(v3, v1) / k;
        if (
            (ds1.Ends && (s < T.AdditiveIdentity || T.MultiplicativeIdentity < s)) ||
            (ds2.Ends && (t < T.AdditiveIdentity || T.MultiplicativeIdentity < t))
        ) return null;
        return Add(ds1.Ab, MulConst(v1, s));
    }

    public static DirectedSegment Projection(C point, DirectedSegment line)
    {
        var (o, v) = (line.Ab, line.Vector);
        var end = Add(o, MulConst(v, DotProduct(v, Sub(point, o)) / Magnitude2(v)));
        return new(point, end, true);
    }

    public static List<C> SortByArgument(IEnumerable<C> points, C origin)
    {
        bool Upper(C v) => v.Y > origin.Y || v.Y == origin.Y && v.X > origin.X;
        var uppers = points.Where(Upper).ToList();
        var lowers = points.Where(p => !Equal(p, origin) && !Upper(p)).ToList();
        int Comparer(C p1, C p2)
        {
            if (Equal(p1, p2)) return 0;
            return CounterClockwise(new DirectedSegment(origin, p1, true), p2) > 0 ? -1 : 1;
        }
        var res = points.Where(p => Equal(p, origin)).ToList();
        uppers.Sort(Comparer);
        lowers.Sort(Comparer);
        res.AddRange(uppers);
        res.AddRange(lowers);
        return res;
    }
}

static class Extensions
{
    public static T[] Repeat<T>(this int time, Func<T> F) => Enumerable.Range(0, time).Select(_ => F()).ToArray();
}

readonly record struct Rational<T> :
    IAdditiveIdentity<Rational<T>, Rational<T>>,
    IAdditionOperators<Rational<T>, Rational<T>, Rational<T>>,
    ISubtractionOperators<Rational<T>, Rational<T>, Rational<T>>,
    IUnaryNegationOperators<Rational<T>, Rational<T>>,
    IMultiplicativeIdentity<Rational<T>, Rational<T>>,
    IMultiplyOperators<Rational<T>, Rational<T>, Rational<T>>,
    IDivisionOperators<Rational<T>, Rational<T>, Rational<T>>,
    IComparable<Rational<T>>,
    IEqualityOperators<Rational<T>, Rational<T>, bool>,
    IComparisonOperators<Rational<T>, Rational<T>, bool>
    where T : IBinaryInteger<T>, IConvertible
{
    public T P { get; private init; }
    public T Q { get; private init; }
    public Rational(T p, T q)
    {
        if (q == T.Zero) throw new DivideByZeroException();
        if (q < T.Zero) (p, q) = (-p, -q);
        var (x, y) = (T.Abs(p), q);
        while (y > T.Zero) (x, y) = (y, x % y);
        (P, Q) = (p / x, q / x);
    }
    public Rational(T p) { (P, Q) = (p, T.One); }
    public static Rational<T> AdditiveIdentity => new(T.Zero); 
    public static Rational<T> MultiplicativeIdentity => new(T.One);

    public static implicit operator Rational<T>(T i) => new(i);
    public static Rational<T> operator -(Rational<T> r) => new(-r.P, r.Q);
    public static Rational<T> operator +(Rational<T> r1, Rational<T> r2) => new(r1.P * r2.Q + r1.Q * r2.P, r1.Q * r2.Q);
    public static Rational<T> operator -(Rational<T> r1, Rational<T> r2) => new(r1.P * r2.Q - r1.Q * r2.P, r1.Q * r2.Q);
    public static Rational<T> operator *(Rational<T> r1, Rational<T> r2) => new(r1.P * r2.P, r1.Q * r2.Q);
    public static Rational<T> operator /(Rational<T> r1, Rational<T> r2) => new(r1.P * r2.Q, r1.Q * r2.P);
    public static bool operator <(Rational<T> r1, Rational<T> r2) => r1.CompareTo(r2) < 0;
    public static bool operator <=(Rational<T> r1, Rational<T> r2) => r1.CompareTo(r2) <= 0;
    public static bool operator >(Rational<T> r1, Rational<T> r2) => r1.CompareTo(r2) > 0;
    public static bool operator >=(Rational<T> r1, Rational<T> r2) => r1.CompareTo(r2) >= 0;
    public int CompareTo(Rational<T> r) => (P * r.Q).CompareTo(Q * r.P);
    public override string ToString() => Q == T.One ? P.ToString()! : (P.ToDouble(null) / Q.ToDouble(null)).ToString();
}

class AtCoder
{
    object? Solve()
    {
        var t = Int();
        var ans = new string[t];
        for (var i = 0; i < t; i++)
        {
            ans[i] = Solve2() ? "Yes" : "No";
        }
        Out(ans);
        return null;
    }

    bool Solve2()
    {
        var p1 = new RationalComplex(Int(), Int());
        var p2 = new RationalComplex(Int(), Int());
        var q1 = new RationalComplex(Int(), Int());
        var q2 = new RationalComplex(Int(), Int());

        if (p1 == q1 && p2 == q2) return true;
        var vp = G.Sub(p1, p2);
        var vq = G.Sub(q1, q2);
        if (G.Magnitude2(vp) <= G.Magnitude2(vq)) return false;
        if (vp.X * vq.Y != vp.Y * vq.X) return false;
        if (G.CounterClockwise(new G.DirectedSegment((0, 0), vp, true), vq) < 0) return false;
        return true;
    }

    public static void Main() => new AtCoder().Run();
    public void Run()
    {
        var res = Solve();
        if (res != null)
        {
            if (res is bool yes) res = yes ? "Yes" : "No";
            sw.WriteLine(res);
        }
        sw.Flush();
    }

    string[] input = Array.Empty<string>();
    int iter = 0;
    readonly StreamWriter sw = new(Console.OpenStandardOutput()) { AutoFlush = false };

    #pragma warning disable IDE0051
    string String()
    {
        while (iter >= input.Length) (input, iter) = (Console.ReadLine()!.Split(' '), 0);
        return input[iter++];
    }
    T Input<T>() where T : IParsable<T> => T.Parse(String(), null);
    int Int() => Input<int>();
    void Out(object? x, string? separator = null)
    {
        separator ??= Environment.NewLine;
        if (x is System.Collections.IEnumerable obj and not string)
        {
            var firstLine = true;
            foreach (var item in obj)
            {
                if (!firstLine) sw.Write(separator);
                firstLine = false;
                sw.Write(item);
            }
        }
        else sw.Write(x);
        sw.WriteLine();
    }
    #pragma warning restore IDE0051
}
0