結果

問題 No.2331 Maximum Quadrilateral
ユーザー lam6er
提出日時 2025-03-20 20:19:19
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,718 bytes
コンパイル時間 177 ms
コンパイル使用メモリ 82,300 KB
実行使用メモリ 66,412 KB
最終ジャッジ日時 2025-03-20 20:20:20
合計ジャッジ時間 3,888 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 1
other AC * 33 WA * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y
    
    def __lt__(self, other):
        return (self.x, self.y) < (other.x, other.y)

def cross(o, a, b):
    return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x)

def convex_hull(points):
    points = sorted(points)
    lower = []
    for p in points:
        while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
            lower.pop()
        lower.append(p)
    upper = []
    for p in reversed(points):
        while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
            upper.pop()
        upper.append(p)
    return lower[:-1] + upper[:-1]

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    points = []
    for _ in range(N):
        x = int(input[idx])
        y = int(input[idx + 1])
        points.append(Point(x, y))
        idx += 2
    hull = convex_hull(points)
    m = len(hull)
    if m < 4:
        print(0)
        return
    max_area = 0
    for i in range(m):
        p = hull[i]
        for j in range(m):
            if i == j:
                continue
            q = hull[j]
            dx = q.x - p.x
            dy = q.y - p.y
            max_cross = -float('inf')
            min_cross = float('inf')
            for r in hull:
                cr = (r.x - p.x) * dy - (r.y - p.y) * dx
                if cr > max_cross:
                    max_cross = cr
                if cr < min_cross:
                    min_cross = cr
            current = (max_cross - min_cross) // 2
            if current > max_area:
                max_area = current
    print(max_area * 2)

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