/// <summary>
/// 偏角クラス
/// (1,0) を 最小として、反時計回りに大小を定義する
/// https://yukicoder.me/users/3692/ai_code/69
/// </summary>
public readonly struct Angle : IComparable<Angle>
{
    public readonly long X;
    public readonly long Y;

    public Angle(long x, long y)
    {
        if (x == 0 && y == 0) throw new ArgumentException("Zero vector is not allowed.");

        var g = Gcd(Math.Abs(x), Math.Abs(y));
        x /= g;
        y /= g;

        X = x;
        Y = y;
    }

    // 上半平面判定
    private bool Half()
    {
        // y > 0 or (y == 0 and x > 0)
        return (Y > 0) || (Y == 0 && X > 0);
    }

    // 外積
    private static long Cross(in Angle a, in Angle b)
    {
        return a.X * b.Y - a.Y * b.X;
    }

    public int CompareTo(Angle other)
    {
        var h1 = Half();
        var h2 = other.Half();

        // 半平面が違うなら上半平面が先
        if (h1 != h2)
            return h1 ? -1 : 1;

        // 同一半平面なら外積符号
        var cross = Cross(this, other);
        if (cross > 0) return -1; // this が反時計回り側 → 角度小
        if (cross < 0) return 1;

        return 0; // 同方向
    }

    public override bool Equals(object obj)
    {
        if (obj is not Angle other) return false;
        return X == other.X && Y == other.Y;
    }

    public override int GetHashCode()
    {
        return HashCode.Combine(X, Y);
    }

    public static bool operator ==(Angle a, Angle b) => a.Equals(b);
    public static bool operator !=(Angle a, Angle b) => !a.Equals(b);
    public static bool operator <(Angle a, Angle b) => a.CompareTo(b) < 0;
    public static bool operator >(Angle a, Angle b) => a.CompareTo(b) > 0;
    public static bool operator <=(Angle a, Angle b) => a.CompareTo(b) <= 0;
    public static bool operator >=(Angle a, Angle b) => a.CompareTo(b) >= 0;

    private static long Gcd(long a, long b)
    {
        while (b != 0)
        {
            var t = a % b;
            a = b;
            b = t;
        }
        return a;
    }

    public override string ToString()
    {
        return $"({X}, {Y})";
    }
}