提出 #72718316

---

ソースコード 拡げる

import sys
from bisect import bisect_left, bisect_right
input = sys.stdin.readline

class Point:
  __slots__ = ('x', 'y', 'region')
  def __init__(self, x, y):
    self.x = x
    self.y = y
    if y < 0 or (y == 0 and x > 0):
      self.region = 0
    else:
      self.region = 1

  def __lt__(self, other):
    if self.region != other.region:
      return self.region < other.region

    cross = self.x * other.y - self.y * other.x
    return cross > 0

def solve():

    N, Q = map(int, input().split())

    points = []
    for i in range(N):
      X, Y = map(int, input().split())
      points.append(Point(X, Y))
    
    original_points = points[:]
    sorted_points = sorted(points)
    
    for _ in range(Q):
      A_idx, B_idx = map(int, input().split())
      p_a = original_points[A_idx - 1]
      p_b = original_points[B_idx - 1]
      idx_start = bisect_right(sorted_points, p_a) - 1
      idx_end = bisect_left(sorted_points, p_b)
      
      if idx_start < idx_end:
        count = (idx_start + 1) + (N - idx_end)
        print(count)
      else:
        count = idx_start - idx_end + 1
        print(count)

solve()

提出情報

ジャッジ結果