結果
問題 |
No.461 三角形はいくつ?
|
ユーザー |
![]() |
提出日時 | 2023-09-19 03:50:34 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,133 bytes |
コンパイル時間 | 141 ms |
コンパイル使用メモリ | 82,168 KB |
実行使用メモリ | 77,792 KB |
最終ジャッジ日時 | 2024-07-05 16:26:50 |
合計ジャッジ時間 | 20,045 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 28 WA * 13 |
ソースコード
import sys input = sys.stdin.readline from bisect import bisect_left from collections import Counter from math import gcd L=[[(0,1)] for i in range(3)] N=int(input()) for i in range(N): p,a,b=map(int,input().split()) G=gcd(a,b) L[p].append((b//G,(a+b)//G)) L[0].sort(key=lambda x:x[0]/x[1]) L[1].sort(key=lambda x:x[0]/x[1]) L[2].sort(key=lambda x:x[0]/x[1]) ANS=0 C=Counter(L[2]) for x0,x1 in L[0]: for y0,y1 in L[1]: if x0*y1+x1*y0>x1*y1: break if x0*y1>x1*y0: MAX=(x0,x1) else: MAX=(y0,y1) m0,m1=MAX OK=-1 NG=len(L[2]) while NG>OK+1: mid=(OK+NG)//2 z0,z1=L[2][mid] if z0*m1<(m1-m0)*z1: OK=mid else: NG=mid #print(x0,x1,y0,y1,L[2],OK) ANS+=OK+1 z0=x1*y1-(x0*y1+x1*y0) z1=x1*y1 G=gcd(z0,z1) z0//=G z1//=G if z0*m1<(m1-m0)*z1 and (z1-z0,z1) in C: ANS-=C[(z0,z1)] #print("!",x0,x1,y0,y1,MAX,z0,z1,C[(z0,z1)]) print(ANS)