結果
| 問題 |
No.3100 Parallel Translated
|
| ユーザー |
 tobisatis
|
| 提出日時 | 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();
}