結果

問題 No.2012 Largest Triangle
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:24:19
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 862 ms / 2,500 ms
コード長 1,804 bytes
コンパイル時間 164 ms
コンパイル使用メモリ 82,720 KB
実行使用メモリ 129,572 KB
最終ジャッジ日時 2025-03-20 20:26:14
合計ジャッジ時間 18,034 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 41
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys

def cross(o, a, b):
    return (a[0] - o[0])*(b[1] - o[1]) - (a[1] - o[1])*(b[0] - o[0])

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 find_max_projection(hull, direction):
    low = 0
    high = len(hull) - 1
    while low < high:
        mid = (low + high) // 2
        current = hull[mid][0] * direction[0] + hull[mid][1] * direction[1]
        next_val = hull[mid+1][0] * direction[0] + hull[mid+1][1] * direction[1]
        if current < next_val:
            low = mid + 1
        else:
            high = mid
    return low

def main():
    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((x, y))
        idx +=2
    hull = convex_hull(points)
    if not hull:
        print(0)
        return
    max_area = 0
    for (x, y) in points:
        direction_d = (y, -x)
        direction_neg = (-y, x)
        idx_d = find_max_projection(hull, direction_d)
        val_d = direction_d[0] * hull[idx_d][0] + direction_d[1] * hull[idx_d][1]
        idx_neg = find_max_projection(hull, direction_neg)
        val_neg = direction_neg[0] * hull[idx_neg][0] + direction_neg[1] * hull[idx_neg][1]
        current_max = max(abs(val_d), abs(val_neg))
        if current_max > max_area:
            max_area = current_max
    print(max_area)

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