結果
| 問題 |
No.3154 convex polygon judge
|
| ユーザー |
 tobisatis
|
| 提出日時 | 2025-05-20 21:51:09 |
| 言語 | C# (.NET 8.0.404) |
| 結果 |
AC
|
| 実行時間 | 1,668 ms / 2,000 ms |
| コード長 | 6,684 bytes |
| コンパイル時間 | 11,967 ms |
| コンパイル使用メモリ | 169,272 KB |
| 実行使用メモリ | 294,488 KB |
| 最終ジャッジ日時 | 2025-05-20 21:51:34 |
| 合計ジャッジ時間 | 24,657 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 44 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (128 ミリ秒)。 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;
var n = int.Parse(Console.ReadLine()!);
var points = new Geometry2D.Point[n];
for (var i = 0; i < n; i++)
{
var l = Console.ReadLine()!.Split(' ');
var x = long.Parse(l[0]);
var y = long.Parse(l[1]);
points[i] = new Geometry2D.Point(x, y);
}
var polygon = new Geometry2D.ConvexHull(points);
Console.WriteLine(polygon.Count == n ? "Yes" : "No");
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 NotImplementedException();
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();
}
}
}