結果

問題 No.3074 Divide Points Fairly
ユーザー titia
提出日時 2025-03-28 22:37:25
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 219 ms / 2,000 ms
コード長 766 bytes
コンパイル時間 391 ms
コンパイル使用メモリ 82,912 KB
実行使用メモリ 87,772 KB
最終ジャッジ日時 2025-03-28 22:37:35
合計ジャッジ時間 9,979 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 42
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline

from random import randint

N=int(input())
P=[list(map(int,input().split())) for i in range(2*N)]

def calc(a,b,c):
    PLUS=0
    MINUS=0
    E=0
    
    for x,y in P:
        if a*x+b*y+c<0:
            MINUS+=1
        if a*x+b*y+c>0:
            PLUS+=1
        if a*x+b*y+c==0:
            E+=1

    return PLUS,MINUS,E

while True:
    a=randint(-10**5,10**5)
    b=randint(-10**5,10**5)

    MIN=-2*10**10
    MAX=2*10**10

    while MAX-MIN>10:
        mid=(MIN+MAX)//2

        P1,M1,E1=calc(a,b,mid)

        if P1>N:
            MAX=mid
        else:
            MIN=mid

    for i in range(MIN,MAX+1):
        P1,M1,E1=calc(a,b,i)


        if P1==M1==N:
            print(a,b,i)
            exit()
0