結果
問題 | No.3100 Parallel Translated |
ユーザー |
|
提出日時 | 2025-04-11 23:19:58 |
言語 | C# (.NET 8.0.404) |
結果 |
AC
|
実行時間 | 94 ms / 2,000 ms |
コード長 | 10,222 bytes |
コンパイル時間 | 10,567 ms |
コンパイル使用メモリ | 169,448 KB |
実行使用メモリ | 199,628 KB |
最終ジャッジ日時 | 2025-04-11 23:20:18 |
合計ジャッジ時間 | 14,541 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 32 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (101 ミリ秒)。 main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
#nullable enable using System.Numerics; void Run() { var n = Int(); var pz = n.Repeat(() => new Geometry2D.Point(Int(), Int())); var h = new Geometry2D.ConvexHull(pz); var s = (ModInt)h.Area2().Value / 2; Out(s); } #region AtCoderIO _io_; var _backend_ = new StandardIOBackend(); _io_ = new(){ Backend = _backend_ }; Run(); _backend_.Flush(); string String() => _io_.Next(); int Int() => int.Parse(String()); void Out(object? x, string? sep = null) => _io_.Out(x, sep); 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 = null) { if (x == null) return; separator ??= Environment.NewLine; if (x is System.Collections.IEnumerable a and not string) { var objects = a.Cast<object>(); if (separator == Environment.NewLine && !objects.Any()) return; x = string.Join(separator, objects); } 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(); } 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 static Number Sqrt(Number s) => throw new Exception(); 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 Number Magnitude() => Number.Sqrt(Magnitude2()); 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 ReadOnlyMemory<Point> Vertices = new(); public Point this[int i] => Vertices.Span[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.Span; 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(); } } } readonly record struct ModInt // : // IEqualityOperators<ModInt, ModInt, bool>, // IAdditiveGroup<ModInt>, // IMultiplicativeGroup<ModInt> { public const int Mod = 998244353; int V { get; init; } public ModInt(long value) { var v = value % Mod; if (v < 0) v += Mod; V = (int)v; } static ModInt New(int value) => new(){ V = value }; public static implicit operator ModInt(long v) => new(v); public static implicit operator int(ModInt modInt) => modInt.V; public static ModInt AdditiveIdentity => New(0); public static ModInt operator +(ModInt a, ModInt b) { var v = a.V + b.V; if (v >= Mod) v -= Mod; return New(v); } public ModInt AdditiveInverse() { if (V == 0) return AdditiveIdentity; return New(Mod - V); } public static ModInt operator -(ModInt a, ModInt b) { var v = a.V - b.V; if (v < 0) v += Mod; return New(v); } public static ModInt MultiplicativeIdentity => New(1); public static ModInt operator *(ModInt a, ModInt b) => New((int)((long)a.V * b.V % Mod)); public ModInt MultiplicativeInverse() { if (V == 0) throw new DivideByZeroException(); var (d, x, _) = ExtendedGCD(V, Mod); if (d > 1) throw new DivideByZeroException(); return x; } public static ModInt operator /(ModInt a, ModInt b) => a * b.MultiplicativeInverse(); static long Power(long v, ulong p, long mod) { var (res, k) = (1L, v); while (p > 0) { if ((p & 1) > 0) res = res * k % mod; k = k * k % mod; p >>= 1; } return res; } public ModInt Power(long p) => p < 0 ? (MultiplicativeIdentity / V).Power(-p) : Power(V, (ulong)p, Mod); static (long d, long x, long y) ExtendedGCD(long a, long b) { var (x0, y0, x1, y1) = (1L, 0L, 0L, 1L); while (b != 0) { var q = a / b; (a, b) = (b, a - q * b); (x0, y0, x1, y1) = (x1, y1, x0 - q * x1, y0 - q * y1); } return (a, x0, y0); } public override string ToString() => V.ToString(); }