< AP25さんのAI生成コード置き場

偏角ソート

日時はサーバーが記録したものです。更新すると更新日時が変わるので、不都合がある場合は新しく投稿してください。

# ABC442-E 偏角ソート & bisect同等関数定義

from functools import cmp_to_key
# 比較関数が「正を返した場合」に要素の順序を入れ替え、「負,零を返した場合」は順序をそのままに保つ

N, Q = map(int, input().split())
XY = [list(map(int, input().split())) for _ in range(N)]
AB = [list(map(int, input().split())) for _ in range(Q)]

def half(v):
    x, y = v
    if y > 0 or (y == 0 and x >0):
        return 0
    else:
        return 1

# CCW昇順ソート用、bがaのCCW側(a<b)なら負値、CW側(a>b)なら正値、同じなら0
def comp(a, b):     
    ha = half(a)
    hb = half(b)
    if ha > hb:
        return 1
    elif ha < hb:
        return -1 
    
    elif ha == hb:
        x0, y0 = a
        x1, y1 = b
        cross = x0 * y1 - y0 * x1   #　外積
        if cross > 0:       # bがaに対してCCW(a<b) =>　そのまま
            return -1
        elif cross < 0:     # bがaに対してCW(a>B)  =>  入れ替え
            return 1
        elif cross == 0:
            return 0

'''
# bisect_left,right同等(ok/ng法)
# bisect_left同等, Z[ok] >= c となるok下限
def searchl(Z, c):
    ng = -1
    ok = len(Z)
    while ok - ng > 1:
        m = (ok + ng) // 2
        if comp(c, Z[m]) <= 0:  # comp(c,Z[m]): Z[m]がc以上であれは零以下
            ok = m
        else:
            ng = m    
    return ok

# bisect_right同等, Z[ok] > cとなるok下限
def searchr(Z, c):
    ng = -1
    ok = len(Z)
    while ok - ng > 1:
        m = (ok + ng) // 2
        if comp(c, Z[m]) < 0:   # comp(c,Z[m]): Z[m]がcより大きければ負値
            ok = m
        else:
            ng = m    
    return ok
'''

# bisect_left,right同等(スタンダード)
def searchl(Z, c):
    # Z: ソート済みのリスト
    # c: 挿入したい値（検索したい値）

    lo = 0          # [0, lo)であればZ[i] < c
    hi = len(Z)     # [hi, N)であればZ[i] >= c

    # loの上限（hiの下限と一致）を求める
    while lo < hi:
        m = (lo + hi) // 2
        # Z[m]がcより小さい場合 = comp(c,Z[m]) <0 のみ、下限(lo)を上げる。 
        # Z[m] >= c の場合は、上限(hi)を下げます。
        if comp(c, Z[m]) > 0:   # if Z[m] < c
            lo = m + 1
        else:
            hi = m
    return lo

def searchr(Z, c):
    # Z: ソート済みのリスト
    # c: 挿入したい値（検索したい値）

    lo = 0          # [0, lo)であればZ[i] <= c
    hi = len(Z)     # [hi, N)であればZ[i] > c

    # loの上限（hiの下限と一致）を求める
    while lo < hi:
        m = (lo + hi) // 2
        # Z[m]がc以下の場合 = comp(c,Z[m]) <=0 のみ、下限(lo)を上げる。 
        # Z[m] > c の場合は、上限(hi)を下げます。
        if comp(c, Z[m]) >= 0:   # if Z[m] <= c
            lo = m + 1
        else:
            hi = m
    return lo

# 元配列使用するのでコピーしてソート
SXY = [(x,y) for x, y in XY]
SXY.sort(key = cmp_to_key(comp))

for a, b in AB:
    xa, ya = XY[a-1]
    xb, yb = XY[b-1]

    # bがaに対して小さいまたは等しい（a=>bのCW移動に角度0をまたがない）
    # ans = (a以下の個数)　- (b未満の個数)
    if comp((xa,ya),(xb,yb)) >= 0:
        n1 = searchr(SXY,(xa, ya))
        n2 = searchl(SXY,(xb, yb))
        ans = n1 - n2
   # bがaに対して大きい（a=>bのCW移動で角度0をまたぐ）
   # ans = N - (aより大かつbより小の個数) =　N - ((b未満の個数）- (a以下の個数)) 
    else:
        n1 = searchl(SXY,(xb, yb))
        n2 = searchr(SXY,(xa, ya))
        ans = N - (n1 - n2)

    print(ans)