#1145702 (C#) No.3438 [Cherry 8th Tune D] 競プロは向いてない

• 問題: No.3438 [Cherry 8th Tune D] 競プロは向いてない
• ユーザー: tobisatis
• 提出日時: 2026-01-23 22:51:20
• 言語: C# (.NET 10.0.101)
• 結果: AC
• 実行時間: 1,824 ms / 3,000 ms
• コード長: 7,505 bytes
• コンパイル時間: 17,198 ms
• コンパイル使用メモリ: 171,144 KB
• 実行使用メモリ: 207,688 KB
• 最終ジャッジ日時: 2026-01-23 22:53:53
• 合計ジャッジ時間: 146,375 ms
• ジャッジサーバーID （参考情報）: judge6 / judge1

ファイルパターン	結果
sample	AC * 1
other	AC * 33

コンパイルメッセージ

  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (146 ミリ秒)。
/home/judge/data/code/Main.cs(172,16): warning CS8618: null 非許容の フィールド 'Vertices' には、コンストラクターの終了時に null 以外の値が入っていなければなりません。'required' 修飾子を追加するか、フィールド を Null 許容として宣言することを検討してください。 [/home/judge/data/code/main.csproj]
  main -> /home/judge/data/code/bin/Release/net10.0/main.dll
  main -> /home/judge/data/code/bin/Release/net10.0/publish/

ソースコード

#nullable enable

#region
var (_input, _iter) = (Array.Empty<string>(), 0);
T I<T>() where T : IParsable<T>
{
    while (_iter >= _input.Length) (_input, _iter) = (Console.ReadLine()!.Split(' '), 0);
    return T.Parse(_input[_iter++], null);
}
#endregion

static T[] Range<T>(int n, Func<T> F) => Enumerable.Range(0, n).Select(_ => F()).ToArray();

string[] Solve()
{
    var n = I<int>();
    var points = Range(n, () => new Geometry2D.Point(I<long>(), I<long>()));
    var polygon = new Geometry2D.ConvexHull(points);
    var d = new Dictionary<(long, long), int>();
    var k = polygon.Count;
    for (var i = 0; i < k; i++)
    {
        var point = polygon[i];
        d[(point.X, point.Y)] = i;
    }
    var ans = new string[n];
    for (var i = 0; i < n; i++)
    {
        var p = points[i];
        var (x, y) = (p.X, p.Y);
        if (d.TryGetValue((x, y), out var j))
        {
            var l = (j - 1 + k) % k;
            var r = (j + 1) % k;
            if (l == r) r = j;
            var ds = new Geometry2D.DirectedSegment(polygon[l], polygon[r], false);
            var v = ds.Vector;
            if (r == j) ans[i] = v.X + " " + v.Y;
            else ans[i] = v.Y + " " + -v.X;
        }
        else ans[i] = "No";
    }
    return ans;
}
var ans = Range(I<int>(), Solve).Select(e => string.Join(Environment.NewLine, e));
Console.WriteLine(string.Join(Environment.NewLine, ans));

static partial class Geometry2D
{
    public readonly struct Number
    {
        public readonly long Value = 0;
        public Number(long value) { Value = value; }
        public static implicit operator long(Number s) => s.Value;
        public static implicit operator Number(long s) => new(s);
        public override string ToString() => Value.ToString();
    }

    public readonly struct Point
    {
        public readonly Number X, Y;
        public Point(Number x, Number y) { (X, Y) = (x, y); }
        public Point AdditionalInverse => new(-X, -Y);
        public static Point operator +(Point l, Point r) => new(l.X + r.X, l.Y + r.Y);
        public static Point operator -(Point l, Point r) => new(l.X - r.X, l.Y - r.Y);

        public Point Mul(Number k) => new(X * k, Y * k);
        public Point Div(Number k) => new(X / k, Y / k);
        public Number DotProduct(Point other) => X * other.X + Y * other.Y;
        public Number CrossProduct(Point other) => X * other.Y - Y * other.X;
        public Number Magnitude2() => DotProduct(this);
        public Point Rotated90() => new(Y, -X);

        public override bool Equals(object? obj) => obj is Point s && s.X == X && s.Y == Y;
        public override int GetHashCode() => (X, Y).GetHashCode();
        public override string ToString() => X + " " + Y;
        public static bool operator ==(Point l, Point r) => l.Equals(r);
        public static bool operator !=(Point l, Point r) => !(l == r);
    }

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

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

    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 (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.Mul(s);
    }

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

// convex hull
static partial class Geometry2D
{
    public class ConvexHull
    {
        public readonly Point[] Vertices;
        public Point this[int i] => Vertices[i];
        public int Count => Vertices.Length;
        public Number Area2()
        {
            Number res = 0;
            for (var i = 0; i < Count; i++) res += this[i].CrossProduct(this[(i + 1) % Count]);
            return res;
        }

        public int Inside(Point point)
        {
            var (li, ri) = (1, Count - 1);
            var (l, r) = (li, ri);
            var vs = Vertices;
            var o = vs[0];
            while (r - l > 1)
            {
                var m = (l + r) >> 1;
                var ccw = CounterClockwise(new DirectedSegment(o, vs[m], true), point);
                if (ccw > 1) l = m; else r = m;
            }
            var ccwl = CounterClockwise(new DirectedSegment(o, vs[l], true), point);
            var ccwr = CounterClockwise(new DirectedSegment(vs[r], o, true), point);
            var ccwm = CounterClockwise(new DirectedSegment(vs[l], vs[r], true), point);
            var ccws = new[]{ ccwl, ccwr, ccwm };
            foreach (var ccw in ccws) if (!(ccw == 0 || ccw > 1)) return -1;
            if (ccwm == 0) return 0;
            if (l == li && ccwl == 0) return 0;
            if (r == ri && ccwr == 0) return 0;
            return 1;
        }

        public ConvexHull(IEnumerable<Point> points)
        {
            if (!points.Any()) return;
            points = points.Distinct();
            var min = points.MinBy(e => (e.Y.Value, e.X.Value));
            var sorted = new List<Point>(new[]{ min });
            sorted.AddRange(SortByArgument(points.Where(e => e != min), min));
            var hull = new Stack<Point>(new[]{ min });
            if (points.Count() > 1)
            {
                var (l1, l2) = (sorted[1], hull.Pop());
                for (var i = 2; i < sorted.Count; i++)
                {
                    var point = sorted[i];
                    var empty = false;
                    while (CounterClockwise(new DirectedSegment(l2, l1, true), point) != 2)
                    {
                        if (hull.Count == 0)
                        {
                            empty = true;
                            break;
                        }
                        (l1, l2) = (l2, hull.Pop());
                    }
                    if (!empty)
                    {
                        hull.Push(l2);
                        l2 = l1;
                    }
                    l1 = point;
                }
                hull.Push(l2);
                hull.Push(l1);
            }
            Vertices = hull.Reverse().ToArray();
        }
    }
}