#989991 (Nim) No.2790 Athena 3

提出ソース
結果

問題	No.2790 Athena 3
ユーザー	👑 seekworser
提出日時	2024-06-21 21:25:20
言語	Nim (2.0.2)
結果	AC
実行時間	2 ms / 2,000 ms
コード長	24,464 bytes
コンパイル時間	4,676 ms
コンパイル使用メモリ	92,852 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-06-21 21:25:26
合計ジャッジ時間	5,521 ms
ジャッジサーバーID （参考情報）	judge5 / judge1
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	2 ms 6,944 KB
testcase_04	AC	1 ms 6,940 KB
testcase_05	AC	2 ms 6,940 KB
testcase_06	AC	1 ms 6,940 KB
testcase_07	AC	2 ms 6,944 KB
testcase_08	AC	2 ms 6,944 KB
testcase_09	AC	2 ms 6,944 KB
testcase_10	AC	2 ms 6,940 KB
testcase_11	AC	1 ms 6,940 KB
testcase_12	AC	2 ms 6,944 KB
testcase_13	AC	1 ms 6,940 KB
testcase_14	AC	2 ms 6,944 KB
testcase_15	AC	1 ms 6,940 KB
testcase_16	AC	1 ms 6,944 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
import macros;macro ImportExpand(s:untyped):untyped = parseStmt($s[2])
# {.checks: off.}
ImportExpand "cplib/tmpl/citrus.nim" <=== "when not declared CPLIB_TMPL_CITRUS:\n    const CPLIB_TMPL_CITRUS* = 1\n    {.warning[UnusedImport]: off.}\n    {.hint[XDeclaredButNotUsed]: off.}\n    import os\n    import algorithm\n    import sequtils\n    import tables\n    import macros\n    import std/math\n    import sets\n    import strutils\n    import strformat\n    import sugar\n    import streams\n    import deques\n    import bitops\n    import heapqueue\n    import options\n    import hashes\n    const MODINT998244353* = 998244353\n    const MODINT1000000007* = 1000000007\n    #[ include cplib/utils/infl ]#\n    when not declared CPLIB_UTILS_INFL:\n        const CPLIB_UTILS_INFL* = 1\n        const INFi32* = 100100111.int32\n        const INFL* = int(3300300300300300491)\n    type double* = float64\n    let readNext = iterator(getsChar: bool = false): string {.closure.} =\n        while true:\n            var si: string\n            try: si = stdin.readLine\n            except EOFError: yield \"\"\n            for s in si.split:\n                if getsChar:\n                    for i in 0..<s.len():\n                        yield s[i..i]\n                else:\n                    if s.isEmptyOrWhitespace: continue\n                    yield s\n    proc input*(t: typedesc[string]): string = readNext()\n    proc input*(t: typedesc[char]): char = readNext(true)[0]\n    proc input*(t: typedesc[int]): int = readNext().parseInt\n    proc input*(t: typedesc[float]): float = readNext().parseFloat\n    macro input*(t: typedesc, n: varargs[int]): untyped =\n        var repStr = \"\"\n        for arg in n:\n            repStr &= &\"({arg.repr}).newSeqWith \"\n        parseExpr(&\"{repStr}input({t})\")\n    macro input*(ts: varargs[auto]): untyped =\n        var tupStr = \"\"\n        for t in ts:\n            tupStr &= &\"input({t.repr}),\"\n        parseExpr(&\"({tupStr})\")\n    macro input*(n: int, ts: varargs[auto]): untyped =\n        for typ in ts:\n            if typ.typeKind != ntyAnything:\n                error(\"Expected typedesc, got \" & typ.repr, typ)\n        parseExpr(&\"({n.repr}).newSeqWith input({ts.repr})\")\n    proc `fmtprint`*(x: int or string or char or bool): string = return $x\n    proc `fmtprint`*(x: float or float32 or float64): string = return &\"{x:.16f}\"\n    proc `fmtprint`*[T](x: seq[T] or Deque[T] or HashSet[T] or set[T]): string = return x.toSeq.join(\" \")\n    proc `fmtprint`*[T, N](x: array[T, N]): string = return x.toSeq.join(\" \")\n    proc `fmtprint`*[T](x: HeapQueue[T]): string =\n        var q = x\n        while q.len != 0:\n            result &= &\"{q.pop()}\"\n            if q.len != 0: result &= \" \"\n    proc `fmtprint`*[T](x: CountTable[T]): string =\n        result = x.pairs.toSeq.mapIt(&\"{it[0]}: {it[1]}\").join(\" \")\n    proc `fmtprint`*[K, V](x: Table[K, V]): string =\n        result = x.pairs.toSeq.mapIt(&\"{it[0]}: {it[1]}\").join(\" \")\n    proc print*(prop: tuple[f: File, sepc: string, endc: string, flush: bool], args: varargs[string, `fmtprint`]) =\n        for i in 0..<len(args):\n            prop.f.write(&\"{args[i]}\")\n            if i != len(args) - 1: prop.f.write(prop.sepc) else: prop.f.write(prop.endc)\n        if prop.flush: prop.f.flushFile()\n    proc print*(args: varargs[string, `fmtprint`]) = print((f: stdout, sepc: \" \", endc: \"\\n\", flush: false), args)\n    const LOCAL_DEBUG{.booldefine.} = false\n    macro getSymbolName(x: typed): string = x.toStrLit\n    macro debug*(args: varargs[untyped]): untyped =\n        when LOCAL_DEBUG:\n            result = newNimNode(nnkStmtList, args)\n            template prop(e: string = \"\"): untyped = (f: stderr, sepc: \"\", endc: e, flush: true)\n            for i, arg in args:\n                if arg.kind == nnkStrLit:\n                    result.add(quote do: print(prop(), \"\\\"\", `arg`, \"\\\"\"))\n                else:\n                    result.add(quote do: print(prop(\": \"), getSymbolName(`arg`)))\n                    result.add(quote do: print(prop(), `arg`))\n                if i != args.len - 1: result.add(quote do: print(prop(), \", \"))\n                else: result.add(quote do: print(prop(), \"\\n\"))\n        else:\n            return (quote do: discard)\n    proc `%`*(x: SomeInteger, y: SomeInteger): int =\n        result = x mod y\n        if y > 0 and result < 0: result += y\n        if y < 0 and result > 0: result += y\n    proc `//`*(x: SomeInteger, y: SomeInteger): int =\n        result = x div y\n        if y > 0 and result * y > x: result -= 1\n        if y < 0 and result * y < x: result -= 1\n    proc `^`*(x: SomeInteger, y: SomeInteger): int = x xor y\n    proc `&`*(x: SomeInteger, y: SomeInteger): int = x and y\n    proc `|`*(x: SomeInteger, y: SomeInteger): int = x or y\n    proc `>>`*(x: SomeInteger, y: SomeInteger): int = x shr y\n    proc `<<`*(x: SomeInteger, y: SomeInteger): int = x shl y\n    proc `%=`*(x: var SomeInteger, y: SomeInteger): void = x = x % y\n    proc `//=`*(x: var SomeInteger, y: SomeInteger): void = x = x // y\n    proc `^=`*(x: var SomeInteger, y: SomeInteger): void = x = x ^ y\n    proc `&=`*(x: var SomeInteger, y: SomeInteger): void = x = x & y\n    proc `|=`*(x: var SomeInteger, y: SomeInteger): void = x = x | y\n    proc `>>=`*(x: var SomeInteger, y: SomeInteger): void = x = x >> y\n    proc `<<=`*(x: var SomeInteger, y: SomeInteger): void = x = x << y\n    proc `[]`*(x, n: int): bool = (x and (1 shl n)) != 0\n    proc `[]=`*(x: var int, n: int, i: bool) =\n        if i: x = x or (1 << n)\n        else: (if x[n]: x = x xor (1 << n))\n    proc pow*(a, n: int, m = INFL): int =\n        var\n            rev = 1\n            a = a\n            n = n\n        while n > 0:\n            if n % 2 != 0: rev = (rev * a) mod m\n            if n > 1: a = (a * a) mod m\n            n >>= 1\n        return rev\n    #[ include cplib/math/isqrt ]#\n    when not declared CPLIB_MATH_ISQRT:\n        const CPLIB_MATH_ISQRT* = 1\n        proc isqrt*(n: int): int =\n            var x = n\n            var y = (x + 1) shr 1\n            while y < x:\n                x = y\n                y = (x + n div x) shr 1\n            return x\n    proc chmax*[T](x: var T, y: T): bool {.discardable.} = (if x < y: (x = y; return true; ) return false)\n    proc chmin*[T](x: var T, y: T): bool {.discardable.} = (if x > y: (x = y; return true; ) return false)\n    proc `max=`*[T](x: var T, y: T) = x = max(x, y)\n    proc `min=`*[T](x: var T, y: T) = x = min(x, y)\n    proc at*(x: char, a = '0'): int = int(x) - int(a)\n    proc Yes*(b: bool = true): void = print(if b: \"Yes\" else: \"No\")\n    proc No*(b: bool = true): void = Yes(not b)\n    proc YES_upper*(b: bool = true): void = print(if b: \"YES\" else: \"NO\")\n    proc NO_upper*(b: bool = true): void = Yes_upper(not b)\n    const DXY* = [(0, -1), (0, 1), (-1, 0), (1, 0)]\n    const DDXY* = [(1, -1), (1, 0), (1, 1), (0, -1), (0, 1), (-1, -1), (-1, 0), (-1, 1)]\n    macro exit*(statement: untyped): untyped = (quote do: (`statement`; quit()))\n    proc initHashSet[T](): Hashset[T] = initHashSet[T](0)\n"
ImportExpand "cplib/geometry/base.nim" <=== "when not declared CPLIB_GEOMETRY_BASE:\n    const CPLIB_GEOMETRY_BASE* = 1\n    import hashes\n    import strformat\n    type Point*[T] = object\n        x*, y*: T\n    var GEOMETRY_EPS* = 1e-10\n\n    proc initPoint*[T](p: (T, T)): Point[T] =\n        ##点を (p[0], p[1]) で初期化\n        Point[T](x: p[0], y: p[1])\n    proc initPoint*[T](x, y: T): Point[T] =\n        ##点を (x, y) で初期化\n        Point[T](x: x, y: y)\n\n    proc `+`*[T](p: Point[T]): Point[T] = p\n    proc `-`*[T](p: Point[T]): Point[T] = Point[T](x: -p.x, y: -p.y)\n    proc `+=`*[T](p: var Point[T], q: Point[T]) = (p.x += q.x; p.y += q.y)\n    proc `-=`*[T](p: var Point[T], q: Point[T]) = (p.x -= q.x; p.y -= q.y)\n    proc `*=`*[S](p: var Point[SomeFloat], x: S) = (p.x *= float(x); p.y *= float(x))\n    proc `*=`*[T, S](p: var Point[T], x: S) = (p.x *= x; p.y *= x)\n    proc `/=`*[S](p: var Point[SomeFloat], x: S) = (p.x /= float(x); p.y /= float(x))\n    proc `/=`*[T, S](p: var Point[T], x: S) = (p.x /= x; p.y /= x)\n    proc dot*[T](p, q: Point[T]): T =\n        ##2点p,qの内積 (p.x * q.x + p.y * q.y)\n        p.x * q.x + p.y * q.y\n    proc cross*[T](p, q: Point[T]): T =\n        ##2点p,qの外積 (p.x * q.y - p.y * q.x)\n        p.x * q.y - p.y * q.x\n    proc `*`*[T](p, q: Point[T]): T = dot(p, q)\n    proc `@`*[T](p, q: Point[T]): T = cross(p, q)\n    proc norm*[T](p: Point[T]): T =\n        ##pのノルム (p.x * p.x + p.y * p.y)\n        dot(p, p)\n    proc `$`*[T](p: Point[T]): string = &\"({p.x}, {p.y})\"\n\n    proc geometry_eq*[T, S](x: T, y: S): bool = x == y\n    proc geometry_eq*(x, y: SomeFloat): bool = (abs(x - y) < GEOMETRY_EPS * x) or (abs(x - y) < GEOMETRY_EPS)\n    proc geometry_eq*(x: int, y: SomeFloat): bool = geometry_eq(float(x), y)\n    proc geometry_eq*(x: SomeFloat, y: int): bool = geometry_eq(x, float(y))\n    proc geometry_neq*[T, S](x: T, y: S): bool = not geometry_eq(x, y)\n    proc geometry_ge*[T, S](x: T, y: S): bool = geometry_eq(x, y) or (x > y)\n    proc geometry_ge*(x: int, y: SomeFloat): bool = geometry_ge(float(x), y)\n    proc geometry_ge*(x: SomeFloat, y: int): bool = geometry_ge(x, float(y))\n    proc geometry_le*[T, S](x: T, y: S): bool = geometry_eq(x, y) or (x < y)\n    proc geometry_le*(x: int, y: SomeFloat): bool = geometry_eq(float(x), y)\n    proc geometry_le*(x: SomeFloat, y: int): bool = geometry_eq(x, float(y))\n    proc geometry_gt*[T, S](x: T, y: S): bool = not geometry_le(x, y)\n    proc geometry_lt*[T, S](x: T, y: S): bool = not geometry_ge(x, y)\n    proc `<`*[T](p, q: Point[T]): bool =\n        if geometry_eq(p.x, q.x): return geometry_lt(p.y, q.y)\n        return geometry_lt(p.x, q.x)\n    proc `>`*[T](p, q: Point[T]): bool =\n        if geometry_eq(p.x, q.x): return geometry_gt(p.y, q.y)\n        return geometry_gt(p.x, q.x)\n    proc `==`*[T](p, q: Point[T]): bool = geometry_eq(p.x, q.x) and geometry_eq(p.y, q.y)\n    proc cmp*[T](p, q: Point[T]): int = (if p < q: -1 elif p == q: 0 else: 1)\n\n\n    proc `+`*[T](p: Point[T], q: Point[T]): Point[T] = (result = p; result += q)\n    proc `-`*[T](p: Point[T], q: Point[T]): Point[T] = (result = p; result -= q)\n    proc `*`*[T, S](p: Point[T], x: S): Point[T] = (result = p; result *= x)\n    proc `*`*[T, S](x: S, p: Point[T]): Point[T] = p * x\n    proc `/`*[T, S](p: Point[T], x: S): Point[T] = (result = p; result /= x)\n    proc `<=`*[T](p, q: Point[T]): bool = not (p > q)\n    proc `>=`*[T](p, q: Point[T]): bool = not (p < q)\n\n    proc hash*[T](p: Point[T]): Hash =\n        result = result !& hash(p.x)\n        result = result !& hash(p.y)\n\n    type Line*[T] = object\n        s*, t*: Point[T]\n\n    proc initLine*[T](s, t: Point[T]): Line[T] =\n        ##2点 (s, t) を通る直線の初期化\n        (assert s != t; return Line[T](s: s, t: t))\n    proc initLine*[T](a, b, c: int): Line[int] = assert false, \"(a,b,c) initialization can't be used for Line[int], please use float or Fraction\"\n    proc initLine*[T](a, b, c: T): Line[T] =\n        ##直線 ax + by + c = 0 の初期化、int 型に対しては使用不可\n        assert geometry_neq(a, T(0)) or geometry_neq(b, T(0))\n        if geometry_eq(b, T(0)):\n            var s = Point[T](x: -c / a, y: T(0))\n            var t = Point[T](x: -c / a, y: T(1))\n            return Line[T](s: s, t: t)\n        else:\n            var s = Point[T](x: T(0), y: -c / b)\n            var t = Point[T](x: T(1), y: (-a-c) / b)\n            return Line[T](s: s, t: t)\n    proc vector*[T](l: Line[T]): Point[T] =\n        ##直線の接ベクトル（直線の方向のベクトル）\n        l.t - l.s\n    proc `$`*[T](l: Line[T]): string = &\"({l.s}, {l.t})\"\n\n\n    type Segment*[T] = object\n        s*, t*: Point[T]\n    proc initSegment*[T](s, t: Point[T]): Segment[T] =\n        ##2点 (s, t) を結ぶ線分の初期化\n        (assert s != t; return Segment[T](s: s, t: t))\n    converter toLine*[T](s: Segment[T]): Line[T] = initLine(s.s, s.t)\n\n"
ImportExpand "cplib/geometry/polygon.nim" <=== "when not declared CPLIB_GEOMETRY_POLYGON:\n    const CPLIB_GEOMETRY_POLYGON* = 1\n    #[ import cplib/geometry/base ]#\n    #[ import cplib/geometry/ccw ]#\n    when not declared CPLIB_GEOMETRY_CCW:\n        const CPLIB_GEOMETRY_CCW* = 1\n        #[ import cplib/geometry/base ]#\n        const\n            COUNTER_CLOCKWISE* = 2\n            CLOCKWISE* = -2\n            ON_SEGMENT* = 0\n            ONLINE_BACK* = 1\n            ONLINE_FRONT* = -1\n    \n        proc ccw*[T](l: Line[T], p: Point[T], strict: bool = false): int =\n            ##直線と点の位置関係を整数で返す. COUNTER_CLOCKWISE: 2, CLOCKWISE: -2, ON_SEGMENT: 0, ONLINE_BACK: 1, ONLINE_FRONT: -1\n            var crs = cross(l.vector, p - l.s)\n            if geometry_lt(crs, 0): return CLOCKWISE\n            if geometry_gt(crs, 0): return COUNTER_CLOCKWISE\n            var d = dot(l.vector, p - l.s)\n            if strict:\n                if geometry_le(d, 0): return ONLINE_BACK\n                if geometry_ge(d, l.vector.norm): return ONLINE_FRONT\n            else:\n                if geometry_lt(d, 0): return ONLINE_BACK\n                if geometry_gt(d, l.vector.norm): return ONLINE_FRONT\n            return ON_SEGMENT\n    \n        proc ccw*[T](p1, p2, p3: Point[T], strict: bool = false): int =\n            ##3点の位置関係を整数で返す. COUNTER_CLOCKWISE: 2, CLOCKWISE: -2, ON_SEGMENT: 0, ONLINE_BACK: 1, ONLINE_FRONT: -1\n            ccw(initLine(p1, p2), p3)\n        proc online*[T](l: Line[T], p: Point[T]): bool =\n            ##点pが直線l上にあるかどうかを判定\n            ccw(l, p) in -1..1\n        proc online*[T](p1, p2, p3: Point[T]): bool =\n            ##点p3が p1, p2 を通る直線上にあるかどうかを判定\n            ccw(p1, p2, p3) in -1..1\n    #[ import cplib/math/fractions ]#\n    when not declared CPLIB_MATH_FRACTIONS:\n        const CPLIB_MATH_FRACTIONS* = 1\n        import strformat\n        import std/math\n        import hashes\n        type Fraction*[T] = object\n            num*, den*: T\n        var FRACTION_REDUCE_LIMIT = 1000000000\n        proc isNaN*(x: Fraction): bool = x.den == 0 and x.num == 0\n        proc reduce*[T](self: var Fraction[T]) =\n            if isNaN(self): return\n            var g = gcd(abs(self.num), abs(self.den))\n            self.num = self.num div g\n            self.den = self.den div g\n            if self.den < 0:\n                self.den *= -1\n                self.num *= -1\n        proc check_and_reduce[T](self: var Fraction[T]) =\n            if self.den < 0 or self.num > FRACTION_REDUCE_LIMIT or self.den > FRACTION_REDUCE_LIMIT: self.reduce()\n        proc initFraction*[T](num, den: T, reduce: bool = true): Fraction[T] =\n            result = Fraction[T](num: num, den: den)\n            if reduce: result.reduce()\n        proc initFraction*[T](num: T): Fraction[T] = Fraction[T](num: num, den: T(1))\n        converter toFraction*[T](x: T): Fraction[T] = initFraction(x)\n        proc `$`*[T](x: Fraction[T]): string =\n            var x = x\n            x.reduce()\n            return &\"{x.num}/{x.den}\"\n        proc inv*[T](x: Fraction[T]): Fraction[T] = Fraction[T](num: x.den, den: x.num)\n        proc abs*[T](x: Fraction[T]): Fraction[T] = (if x.num < 0: Fraction[T](num: -x.num, den: x.den) else: x)\n        proc `-`*[T](x: Fraction[T]): Fraction[T] = Fraction[T](num: -x.num, den: x.den)\n        proc `+=`*[T](x: var Fraction[T], y: Fraction[T]) =\n            if isNaN(x) or isNaN(y):\n                x = initFraction(0, 0)\n                return\n            if x.den == 0 and y.den == 0:\n                if (x.num > 0) == (y.num > 0): return\n                x = initFraction(0, 0)\n                return\n            if x.den == 0 or y.den == 0:\n                if x.den != 0: x = y\n                return\n            x.num = x.num * y.den + y.num * x.den\n            x.den *= y.den\n            x.check_and_reduce()\n        proc `-=`*[T](x: var Fraction[T], y: Fraction[T]) = x += (-y)\n        proc `*=`*[T](x: var Fraction[T], y: Fraction[T]) =\n            if isNaN(x) or isNaN(y):\n                x = initFraction(0, 0)\n                return\n            x.den *= y.den\n            x.num *= y.num\n            x.check_and_reduce()\n        proc `/=`*[T](x: var Fraction[T], y: Fraction[T]) =\n            if isNaN(x) or isNaN(y):\n                x = initFraction(0, 0)\n                return\n            x.den *= y.num\n            x.num *= y.den\n            x.check_and_reduce()\n        proc `>`*[T](x, y: Fraction[T]): bool =\n            if isNaN(x) or isNaN(y): return false\n            if x.den == 0 and y.den == 0: return x.num > y.num\n            x.num * y.den > y.num * x.den\n        proc `<`*[T](x, y: Fraction[T]): bool =\n            if isNaN(x) or isNaN(y): return false\n            if x.den == 0 and y.den == 0: return x.num < y.num\n            x.num * y.den < y.num * x.den\n        proc `==`*[T](x, y: Fraction[T]): bool =\n            if isNaN(x) or isNaN(y): return false\n            if x.den == 0 and y.den == 0: return (x.num div abs(x.num)) * (y.num div abs(y.num)) > 0\n            x.num * y.den == y.num * x.den\n        proc cmp*[T](x, y: Fraction[T]): int = (if x < y: -1 elif x == y: 0 else: 1)\n    \n        proc `+=`*[T](x: var Fraction[T], y: T) = (x += initFraction[T](y))\n        proc `+`*[T](x, y: Fraction[T]): Fraction[T] = (result = x; result += y)\n        proc `+`*[T](x: Fraction[T], y: T): Fraction[T] = (result = x; result += y)\n        proc `+`*[T](x: T, y: Fraction[T]): Fraction[T] = (result = y; result += x)\n        proc `-=`*[T](x: var Fraction[T], y: T) = (x -= initFraction[T](y))\n        proc `-`*[T](x, y: Fraction[T]): Fraction[T] = (result = x; result -= y)\n        proc `-`*[T](x: Fraction[T], y: T): Fraction[T] = (result = x; result -= y)\n        proc `-`*[T](x: T, y: Fraction[T]): Fraction[T] = (result = -y; result += x)\n        proc `*=`*[T](x: var Fraction[T], y: T) = (x *= initFraction[T](y))\n        proc `*`*[T](x, y: Fraction[T]): Fraction[T] = (result = x; result *= y)\n        proc `*`*[T](x: Fraction[T], y: T): Fraction[T] = (result = x; result *= y)\n        proc `*`*[T](x: T, y: Fraction[T]): Fraction[T] = (result = y; result *= x)\n        proc `/=`*[T](x: var Fraction[T], y: T) = (x /= initFraction[T](y))\n        proc `/`*[T](x, y: Fraction[T]): Fraction[T] = (result = x; result /= y)\n        proc `/`*[T](x: Fraction[T], y: T): Fraction[T] = (result = x; result /= y)\n        proc `/`*[T](x: T, y: Fraction[T]): Fraction[T] = (result = y.inv(); result *= x)\n        proc `>`*[T](x: Fraction[T], y: T): bool = x > initFraction[T](y)\n        proc `>`*[T](x: T, y: Fraction[T]): bool = initFraction[T](x) > y\n        proc `<=`*[T](x: Fraction[T], y: Fraction[T] or T): bool = not (x > y)\n        proc `<=`*[T](x: T, y: Fraction[T]): bool = not(x > y)\n        proc `<`*[T](x: Fraction[T], y: T): bool = x < initFraction[T](y)\n        proc `<`*[T](x: T, y: Fraction[T]): bool = initFraction[T](x) < y\n        proc `>=`*[T](x: Fraction[T], y: Fraction[T] or T): bool = not (x < y)\n        proc `>=`*[T](x: T, y: Fraction[T]): bool = not(x < y)\n        proc `==`*[T](x: Fraction[T], y: T): bool = x == initFraction[T](y)\n        proc `==`*[T](x: T, y: Fraction[T]): bool = initFraction[T](x) == y\n        proc cmp*[T](x: Fraction[T], y: T): int = cmp(x, initFraction[T](y))\n        proc cmp*[T](x: T, y: Fraction[T]): int = cmp(initFraction[T](x), y)\n        proc hash*[T](x: Fraction[T]): Hash =\n            var x = x\n            x.reduce()\n            result = result !& hash(x.num)\n            result = result !& hash(x.den)\n        proc toFloat*[T](x: Fraction[T]): float =\n            x.num / x.den\n        proc pow*[T](x: Fraction[T], n: int): Fraction[T] =\n            result = initFraction[T](1)\n            var x = x\n            var n = n\n            while n > 0:\n                if (n and 1) == 1: result *= x\n                x *= x\n                n = n shr 1\n    import algorithm\n    type Polygon*[T] = object\n        v*: seq[Point[T]]\n    proc len*[T](poly: Polygon[T]): int = poly.v.len\n    iterator items*[T](poly: Polygon[T]): Point[T] =\n        for item in poly.v: yield item\n\n    proc initPolygon*[T](v: seq[Point[T]]): Polygon[T] =\n        ## 頂点列 v の多角形型を初期化\n        Polygon[T](v: v)\n    proc area*(p: Polygon[int]): int =\n        ## 多角形の面積の2倍、頂点列が時計回りの場合負の数が返る\n        for i in 0..<p.v.len: result += cross(p.v[i], p.v[(i+1) mod p.v.len])\n    proc area*[T](p: Polygon[Fraction[T]]): Fraction[T] =\n        ## 多角形の面積、頂点列が時計回りの場合負の数が返る\n        result = initFraction(0)\n        for i in 0..<p.v.len: result += cross(p.v[i], p.v[(i+1) mod p.v.len]) / 2\n    proc area*(p: Polygon[float]): float =\n        ## 多角形の面積、頂点列が時計回りの場合負の数が返る\n        for i in 0..<p.v.len: result += cross(p.v[i], p.v[(i+1) mod p.v.len]) / 2.0\n\n    proc is_convex_ccw*[T](poly: Polygon[T], strict: bool = true): bool =\n        ## 頂点列が反時計回りの多角形に対して、凸かどうかを判定\n        for i in 0..<poly.len:\n            var ccwi = ccw(poly.v[i], poly.v[(i+1) mod poly.len], poly.v[(i+2) mod poly.len])\n            if strict and ccwi != COUNTER_CLOCKWISE: return false\n            if (not strict) and ccwi == CLOCKWISE: return false\n        return true\n    proc is_convex*[T](poly: Polygon[T], strict: bool = true): bool =\n        ## 多角形が凸かどうかを判定、ちょうど 180 度の内角を許容する場合は strict = false を設定\n        if is_convex_ccw(poly, strict): return true\n        var pn = Polygon[T](v: poly.v.reversed)\n        return is_convex_ccw(pn, strict)\n\n    proc on_edge*[T](poly: Polygon[T], p: Point[T]): bool =\n        ## 点 p が多角形 poly の辺上にあるかどうかを判定\n        for i in 0..<poly.len:\n            if ccw(poly.v[i], poly.v[(i+1) mod poly.len], p) == ON_SEGMENT: return true\n        return false\n    proc contains*[T](poly: Polygon[T], p: Point[T], strict: bool = false): bool =\n        ## 自己交差のない多角形 poly 内に点 p が存在するかを判定、辺上にある場合を含めない場合は strict = true を設定\n        if on_edge(poly, p):\n            if strict: return false\n            else: return true\n        result = false\n        for i in 0..<poly.len:\n            var a = poly.v[i] - p\n            var b = poly.v[(i+1) mod poly.len] - p\n            if a.y > b.y: swap(a, b)\n            if geometry_le(a.y, 0) and geometry_gt(b.y, 0) and geometry_lt(cross(a, b), 0):\n                result = not result\n\n    proc convex_hull*[T](v: seq[Point[T]], strict: bool = true): Polygon[T] =\n        ## 点群 v の凸包\n        var n = v.len\n        if n < 3: return Polygon[T](v: v)\n        var s = v.sorted\n        var vi = s[0..1]\n        for i in 2..<n:\n            if strict:\n                while vi.len >= 2 and ccw(vi[^2], vi[^1], s[i]) != COUNTER_CLOCKWISE: discard vi.pop\n            else:\n                while vi.len >= 2 and ccw(vi[^2], vi[^1], s[i]) == CLOCKWISE: discard vi.pop\n            vi.add(s[i])\n        var lower_size = vi.len\n        for i in countdown(n-2, 0):\n            if strict:\n                while vi.len > lower_size and ccw(vi[^2], vi[^1], s[i]) != COUNTER_CLOCKWISE: discard vi.pop\n            else:\n                while vi.len > lower_size and ccw(vi[^2], vi[^1], s[i]) == CLOCKWISE: discard vi.pop\n            vi.add(s[i])\n        vi.delete(0)\n        return Polygon[T](v: vi)\n"

var dxy = @[initPoint(0, 1), initPoint(0, -1), initPoint(1, 0), initPoint(-1, 0)]

var a = initPoint(input(int), input(int))
var b = initPoint(input(int), input(int))
var c = initPoint(input(int), input(int))

var ans = 0
for da in dxy:
    for db in dxy:
        for dc in dxy:
            var poly = initPolygon(@[a + da, b + db, c + dc])
            ans.max = abs(poly.area)
print(float(ans) / 2.0)
yukicoder

結果

テストケース

ソースコード
