結果

問題 No.3100 Parallel Translated
コンテスト
ユーザー Mao-beta
提出日時 2025-04-13 23:16:11
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 5,581 bytes
コンパイル時間 477 ms
コンパイル使用メモリ 82,348 KB
実行使用メモリ 58,956 KB
最終ジャッジ日時 2025-04-13 23:16:15
合計ジャッジ時間 3,777 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 2
other WA * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math
import bisect
from heapq import heapify, heappop, heappush
from collections import deque, defaultdict, Counter
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product

sys.set_int_max_str_digits(10 ** 6)
sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
MOD99 = 998244353

input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()
SMI = lambda: input().split()
SLI = lambda: list(SMI())
EI = lambda m: [NLI() for _ in range(m)]


def get_y(x, x1, y1, x2, y2):
    """ (x1,y1) と (x2,y2) を結ぶ線分の、x1<=x<=x2 である x の時の y 座標 """
    assert x1 - 1e-6 <= x <= x2 + 1e-6
    dx = x2 - x1
    if dx == 0:
        return y2
    return (y1 * (x2 - x) + y2 * (x - x1)) / dx


def cross_point(x0, y0, x1, y1, x2, y2, x3, y3):
    a0 = x1 - x0
    b0 = y1 - y0
    a2 = x3 - x2
    b2 = y3 - y2

    d = a0 * b2 - a2 * b0
    if d == 0:
        return None

    sn = b2 * (x2 - x0) - a2 * (y2 - y0)
    if not (0 <= sn <= d or d <= sn <= 0):
        return None

    rn = b0 * (x2 - x0) - a0 * (y2 - y0)
    if not (0 <= rn <= d or d <= rn <= 0):
        return None

    return x0 + a0 * sn / d, y0 + b0 * sn / d


def push_rrr(cp, rrr):
    """ 昇順にソートされていて、末尾数項のみが追加点cpと比較して大きい可能性があるrrrに、cpを追加する """
    if rrr:
        if rrr[-1] < cp:
            rrr.append(cp)
        elif rrr[-1] > cp:
            i = len(rrr) - 2
            while i >= 0 and rrr[i] >= cp:
                i -= 1
            if rrr[i + 1] > cp:
                rrr.insert(i + 1, cp)
    else:
        rrr.append(cp)


def add_next_cross(is_hi, ai, bli, bhi, aaa, bbb, n, m, rlo, rhi):
    if bli == bhi == -1:
        return

    x0, y0 = aaa[ai]
    if is_hi:
        x1, y1 = aaa[(ai - 1) % n]
    else:
        x1, y1 = aaa[(ai + 1) % n]
    x2, y2 = bbb[bli]
    x3, y3 = bbb[(bli + 1) % m]
    cp = cross_point(x0, y0, x1, y1, x2, y2, x3, y3)
    # print(f'{x0},{y0},{x1},{y1},{x2},{y2},{x3},{y3},{cp}')
    if cp is not None:
        push_rrr(cp, rlo)
        if is_hi:
            push_rrr(cp, rhi)

    x2, y2 = bbb[bhi]
    x3, y3 = bbb[(bhi - 1) % m]
    cp = cross_point(x0, y0, x1, y1, x2, y2, x3, y3)
    # print(f'{x0},{y0},{x1},{y1},{x2},{y2},{x3},{y3},{cp}')
    if cp is not None:
        push_rrr(cp, rhi)
        if not is_hi:
            push_rrr(cp, rlo)


def add_corner(x, y, bli, bhi, bbb, m, rrr, rrr2=None):
    if bli == bhi == -1:
        return
    if rrr and rrr[-1] == (x, y):
        return
    aly = get_y(x, *bbb[bli], *bbb[(bli + 1) % m])
    ahy = get_y(x, *bbb[bhi], *bbb[(bhi - 1) % m])
    if aly <= y <= ahy:
        push_rrr((x, y), rrr)
        if rrr2 is not None:
            push_rrr((x, y), rrr2)


def get_intersection(ppp, qqq):
    """
    凸多角形ppp, qqq(頂点のリスト)の共通部分の頂点群を返す
    """
    n = len(ppp)
    m = len(qqq)
    ppp_events = [(x, y, 0, i) for i, (x, y) in enumerate(ppp)]
    qqq_events = [(x, y, 1, i) for i, (x, y) in enumerate(qqq)]

    pi_min = min(ppp_events)[3]
    pi_max = max(ppp_events)[3]
    qi_min = min(qqq_events)[3]
    qi_max = max(qqq_events)[3]

    events = ppp_events + qqq_events
    events.sort()

    pli = phi = qli = qhi = -1
    rlo = []
    rhi = []

    for x, y, pq, i in events:

        if pq == 0 and i == pi_min:
            pli = phi = i
            add_next_cross(True, pli, qli, qhi, ppp, qqq, n, m, rlo, rhi)
            add_next_cross(False, phi, qli, qhi, ppp, qqq, n, m, rlo, rhi)
            add_corner(x, y, qli, qhi, qqq, m, rlo, rhi)
            continue
        if pq == 1 and i == qi_min:
            qli = qhi = i
            add_next_cross(True, qli, pli, phi, qqq, ppp, m, n, rlo, rhi)
            add_next_cross(False, qhi, pli, phi, qqq, ppp, m, n, rlo, rhi)
            add_corner(x, y, pli, phi, ppp, n, rlo, rhi)
            continue

        if pq == 0:
            if i == (pli + 1) % n:
                add_corner(x, y, qli, qhi, qqq, m, rlo)
                pli = i
                if pli != pi_max:
                    add_next_cross(False, pli, qli, qhi, ppp, qqq, n, m, rlo, rhi)
            if i == (phi - 1) % n:
                add_corner(x, y, qli, qhi, qqq, m, rhi)
                phi = i
                if phi != pi_max:
                    add_next_cross(True, phi, qli, qhi, ppp, qqq, n, m, rlo, rhi)
        else:
            if i == (qli + 1) % m:
                add_corner(x, y, pli, phi, ppp, n, rlo)
                qli = i
                if qli != qi_max:
                    add_next_cross(False, qli, pli, phi, qqq, ppp, m, n, rlo, rhi)
            if i == (qhi - 1) % m:
                add_corner(x, y, pli, phi, ppp, n, rhi)
                qhi = i
                if qhi != qi_max:
                    add_next_cross(True, qhi, pli, phi, qqq, ppp, m, n, rlo, rhi)

        if pli == phi == pi_max or qli == qhi == qi_max:
            break

    if len(rlo) == len(rhi) == 0:
        return []

    assert len(rlo) > 0 and len(rhi) > 0
    assert rlo[0] == rhi[0]
    assert rlo[-1] == rhi[-1]

    if len(rlo) + len(rhi) <= 4:
        return []

    rlo.extend(rhi[-2:0:-1])
    return rlo


def polygon_area(N, P):
    return abs(sum((P[i][0]*P[i-1][1] - P[i][1]*P[i-1][0]) % MOD99 for i in range(N))) * pow(2, MOD99-2, MOD99) % MOD99


def main():
    N = NI()
    XY = EI(N)
    print(polygon_area(N, XY))


if __name__ == "__main__":
    main()
0