結果

問題 No.947 ABC包囲網
コンテスト
ユーザー titia
提出日時 2019-12-10 01:56:30
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 872 bytes
コンパイル時間 501 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 82,432 KB
最終ジャッジ日時 2024-06-23 12:44:01
合計ジャッジ時間 10,659 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17 WA * 12 TLE * 2 -- * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

n=int(input())
P=[tuple(map(int,input().split())) for i in range(n)]

Q=[]

import math

for x,y in P:
    if x==y==0:
        continue
    Q.append(math.atan2(y,x))

#print(Q)

Q.sort()

ANS=0
import bisect

for i in range(n-1):
    for j in range(i+1,n):
        if Q[j]-Q[i]>=math.pi:
            continue

        if Q[i]<=0 and Q[j]<=0:
            x=bisect.bisect_right(Q,Q[i]+math.pi)
            y=bisect.bisect_left(Q,Q[j]+math.pi)

            #print(i,j,x,y)
            ANS+=y-x

        elif Q[i]>=0 and Q[j]>=0:
            x=bisect.bisect_right(Q,Q[i]-math.pi)
            y=bisect.bisect_left(Q,Q[j]-math.pi)

            #print(i,j,x,y)
            ANS+=y-x

        else:
            x=bisect.bisect_right(Q,Q[i]+math.pi)
            y=bisect.bisect_left(Q,Q[j]-math.pi)

            #print(i,j,x,y)
            ANS+=(n-x)+y

print(ANS//2)
0