結果

問題 No.245 貫け！
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:22:49
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,852 bytes
コンパイル時間 168 ms
コンパイル使用メモリ 83,032 KB
実行使用メモリ 91,528 KB
最終ジャッジ日時 2025-03-20 20:25:02
合計ジャッジ時間 12,870 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 8 TLE * 1 -- * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

from fractions import Fraction
import sys

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    segments = []
    for _ in range(N):
        a = int(input[ptr])
        b = int(input[ptr+1])
        c = int(input[ptr+2])
        d = int(input[ptr+3])
        ptr += 4
        p1 = (Fraction(a), Fraction(b))
        p2 = (Fraction(c), Fraction(d))
        segments.append((p1, p2))
    
    candidate_points = set()
    for seg in segments:
        p1, p2 = seg
        candidate_points.add((p1[0], p1[1]))
        candidate_points.add((p2[0], p2[1]))
        mid_x = (p1[0] + p2[0]) / Fraction(2)
        mid_y = (p1[1] + p2[1]) / Fraction(2)
        candidate_points.add((mid_x, mid_y))
    
    points = list(candidate_points)
    max_count = 0
    
    for i in range(len(points)):
        p1 = points[i]
        x1, y1 = p1
        for j in range(i + 1, len(points)):
            p2 = points[j]
            x2, y2 = p2
            
            if x1 == x2 and y1 == y2:
                continue
            
            dx = x2 - x1
            dy = y2 - y1
            a = dy
            b = -dx
            c = dx * y1 - dy * x1
            
            count = 0
            for seg in segments:
                (s_p1, s_p2) = seg
                x_a, y_a = s_p1
                x_b, y_b = s_p2
                
                valA = a * x_a + b * y_a + c
                valB = a * x_b + b * y_b + c
                
                if valA == 0 or valB == 0:
                    count += 1
                    continue
                if valA * valB < 0:
                    count += 1
            
            if count > max_count:
                max_count = count
    
    if max_count == 0 and N >= 1:
        max_count = 1
    
    print(max_count)

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