結果

問題 No.3005 トレミーの問題
ユーザー tobisatis
提出日時 2025-01-17 22:33:27
言語 C#
(.NET 8.0.404)
結果
AC  
実行時間 80 ms / 2,000 ms
コード長 3,792 bytes
コンパイル時間 11,333 ms
コンパイル使用メモリ 170,944 KB
実行使用メモリ 195,756 KB
最終ジャッジ日時 2025-01-17 22:34:33
合計ジャッジ時間 15,362 ms
ジャッジサーバーID
(参考情報)
judge2 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (141 ミリ秒)。
  main -> /home/judge/data/code/bin/Release/net8.0/main.dll
  main -> /home/judge/data/code/bin/Release/net8.0/publish/

ソースコード

diff #

#nullable enable

using System.Numerics;

void Solve()
{
    var pz = new Point[4];
    for (var i = 0; i < 4; i++)
    {
        var x = Int();
        var y = Int();
        pz[i] = new(x, y);
    }
    var m01 = (pz[0] + pz[1]) * 0.5;
    var m02 = (pz[0] + pz[2]) * 0.5;
    var d1 = new G.DirectedSegment(m01, pz[0], false).Rotated90();
    var d2 = new G.DirectedSegment(m02, pz[0], false).Rotated90();
    if (Point.Sign(Math.Min(d1.Vector.Magnitude2, d2.Vector.Magnitude2)) == 0)
    {
        Out("NO");
        return;
    }
    var c = G.Intersection(d1, d2);
    if (c == null)
    {
        Out("NO");
        return;
    }
    var r0 = new G.DirectedSegment(c.Value, pz[0], false);
    var r3 = new G.DirectedSegment(c.Value, pz[3], false);
    var d = r0.Vector.Magnitude2 - r3.Vector.Magnitude2;
    Out(Point.Sign(d) == 0 ? "YES" : "NO");
}

#region
AtCoderIO _io_;
var _backend_ = new StandardIOBackend();
_io_ = new(){ Backend = _backend_ };
Solve();
_backend_.Flush();

string String() => _io_.Next();
int Int() => int.Parse(String());
void Out(object? x, string? sep = null) => _io_.Out(x, sep ?? Environment.NewLine);

class AtCoderIO
{
    public required StandardIOBackend Backend { get; init; }

    Memory<string> _input = Array.Empty<string>();
    int _iter = 0;
    public string Next()
    {
        while (_iter >= _input.Length) (_input, _iter) = (Backend.ReadLine().Split(' '), 0);
        return _input.Span[_iter++];
    }

    public void Out(object? x, string separator)
    {
        if (x is System.Collections.IEnumerable obj and not string)
            x = string.Join(separator, obj.Cast<object>());
        Backend.WriteLine(x);
    }
}

class StandardIOBackend
{
    readonly StreamReader _sr = new(Console.OpenStandardInput());
    readonly StreamWriter _sw = new(Console.OpenStandardOutput()) { AutoFlush = false };
    public string ReadLine() => _sr.ReadLine()!;
    public void WriteLine(object? value) => _sw.WriteLine(value);
    public void Flush() => _sw.Flush();
}
#endregion

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

readonly struct Point
{
    const double EPS = 1.0e-12;
    readonly Complex C { get; }
    public double X => C.Real;
    public double Y => C.Imaginary;
    public Point(double x, double y) { C = new(x, y); }
    Point(Complex c) { C = c; }

    public static Point operator +(Point l, Point r) => new(l.C + r.C);
    public static Point operator -(Point l, Point r) => new(l.C - r.C);
    public static Point operator *(Point l, Point r) => new(l.C * r.C);
    public static Point operator *(Point c, double k) => new (c.C * k);
    public double DotProduct(Point other) => X * other.X + Y * other.Y;
    public double CrossProduct(Point other) => X * other.Y - Y * other.X;
    public double Magnitude2 => DotProduct(this);
    public static int Sign(double v) => Math.Abs(v) <= EPS ? 0 : v.CompareTo(0);

    public static readonly Point R90 = new(0, 1);
}

static partial class G
{
    public record struct DirectedSegment(Point Ab, Point Ad, bool Ends)
    {
        public readonly Point Vector => Ad - Ab;
        public readonly DirectedSegment Rotated90() =>
            new(Ab, (Ad - Ab) * Point.R90 + Ab, Ends);
    }

    public static Point? Intersection(DirectedSegment ds1, DirectedSegment ds2)
    {
        var (v1, v2, v3) = (ds1.Vector, ds2.Vector, ds2.Ab - ds1.Ab);
        var k = v1.CrossProduct(v2);
        if (Point.Sign(k) == 0) return null;
        var s = v3.CrossProduct(v2) / k;
        var t = v3.CrossProduct(v1) / k;
        if (
            (ds1.Ends && (s < 0 || 1 < s)) ||
            (ds2.Ends && (t < 0 || 1 < t))
        ) return null;
        return ds1.Ab + v1 * s;
    }
}
0