#`. 最强选手

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z [ \ ] ^ _ ` a b c d e f g h
    Type: RemoteJudge 1000ms 256MiB

最强选手

题面描述

OI 比赛一般考察选手的原题能力（Original Problem）和想象能力（Imagination）。

已知现在有 nn 个选手，他们的年级从大到小依次排列。这些选手的能力可以由 (Oi,Ii)(O_i, I_i) 描述，表示他的原题能力、想象能力分别为 Oi,IiO_i, I_i。

为了评判选手的综合能力，评委组制定了两个权重 O,I\Omicron, \Iota，表示一个选手的综合能力为 $\frac{\Omicron \times O_i + \Iota \times I_i}{\Omicron + \Iota}$。根据综合能力，我们可以给选手排一个名次，并且选出一个第一名。由于这样很容易出现多人能力相同的情况，为了尊重高年级的选手，评委组决定选择综合能力最强的选手中，年级最大的（也就是编号最小的）选手作为第一名。

由于 OI 的不断发展，两个权重 O,I\Omicron, \Iota 也会不断变化。已知在其中的 mm 个时刻，权值为 Oj,Ij\Omicron_j, \Iota_j，请算出这 mm 个时刻对应的最强选手，输出他们的编号即可。

输入格式

第一行两个正整数 n,mn, m，表示选手的个数，权重的组数。

接下来 nn 行，每行两个自然数 Oi,IiO_i, I_i，表示选手的两种能力。

接下来 mm 行，每行两个自然数 Oj,Ij\Omicron_j, \Iota_j，表示某个时刻的权重。

输出格式

对于每一种权重，输出最强的选手编号。

样例

3 3
1 0
0 2
0 1
1 1
2 2
2 1

2
2
1

说明/提示

当权重为 (1,1)(1, 1) 时，三位选手的综合能力分别为 12,1,12\frac{1}{2}, 1, \frac{1}{2}，因此最强的选手是 22 号选手。

当权重为 (2,1)(2, 1) 时，三位选手的综合能力分别为 23,23,13\frac{2}{3}, \frac{2}{3}, \frac{1}{3}，因此最强选手是 11 号选手。

对于 100%100\% 的数据，1≤n,m≤5×1051 \le n, m \le 5 \times 10^5。

对于所有 1≤i≤n1 \le i \le n，保证 0≤Oi,Ii≤1060 \le O_i, I_i \le 10^6，且 Oi+Ii≥1O_i + I_i \ge 1，且对于任意 1≤j≤n,i≠j1 \le j \le n, i \ne j，有 Oi≠OjO_i \ne O_j 或 Ii≠IjI_i \ne I_j。

对于所有 1≤i≤m1 \le i \le m，保证 0≤Oi,Ii≤1060 \le \Omicron_i, \Iota_i \le 10^6，且 Oi+Ii≥1\Omicron_i + \Iota_i \ge 1，且对于任意 1≤j≤m,i≠j1 \le j \le m, i \ne j，有 Oi≠Oj\Omicron_i \ne \Omicron_j 或 Ii≠Ij\Iota_i \ne \Iota_j。

国庆提高/省选组比赛

Attended
Status
Live... (Attended)
Rule
IOI
Problem
40
Start at
2025-10-15 19:32
End at
2025-11-16 0:00
Duration
1104 hour(s)
Host
Partic.
85
  1. About
  2. Contact Us
  3. Privacy
  4. Terms of Service
  5. Copyright Complaint
  6. Language
  7. Legacy mode
  8. Theme
  2. 粤ICP备2021104657号
  3. Worker 0, 21ms
  4. Powered by Hydro v4.14.1 Community