C. Biathlon
传送门：Problem - C - Codeforces
Perhaps many have heard that the World Biathlon Championship has finished. Although our hero Valera was not present at this spectacular event himself and only watched it on TV, it excited him so much that he decided to enroll in a biathlon section.
Of course, biathlon as any sport, proved very difficult in practice. It takes much time and effort. Workouts, workouts, and workouts, — that's what awaited Valera on his way to great achievements in biathlon.
As for the workouts, you all probably know that every professional biathlete should ski fast and shoot precisely at the shooting range. Only in this case you can hope to be successful, because running and shooting are the two main components of biathlon. Valera has been diligent in his ski trainings, which is why he runs really fast, however, his shooting accuracy is nothing to write home about.
On a biathlon base where Valera is preparing for the competition, there is a huge rifle range with n targets. Each target have shape of a circle, and the center of each circle is located on the Ox axis. At the last training session Valera made the total of m shots. To make monitoring of his own results easier for him, one rather well-known programmer (of course it is you) was commissioned to write a program that would reveal how many and which targets Valera hit. More specifically, for each target the program must print the number of the first successful shot (in the target), or "-1" if this was not hit. The target is considered hit if the shot is inside the circle or on its boundary. Valera is counting on you and perhaps, thanks to you he will one day win international competitions.
Input
The first line of the input file contains the integer n (1 ≤ n ≤ 10^4), which is the number of targets. The next n lines contain descriptions of the targets. Each target is a circle whose center is located on the Ox axis. Each circle is given by its coordinate of the center x ( - 2·10^4 ≤ x ≤ 2·10^4) and its radius r (1 ≤ r ≤ 1000). It is guaranteed that no two targets coincide, intersect or are nested into each other, but they can touch each other.
The next line contains integer m (1 ≤ m ≤ 2·10^5), which is the number of shots. Next m lines contain descriptions of the shots, which are points on the plane, given by their coordinates x and y ( - 2·10^4 ≤ x, y ≤ 2·10^4).
All the numbers in the input are integers.
Targets and shots are numbered starting from one in the order of the input.
Output
Print on the first line a single number, the number of targets hit by Valera. Print on the second line for each of the targets the number of its first hit or "-1" (without quotes) if this number does not exist. Separate numbers with spaces.
题目大意
也许很多人都听说世界冬季两项锦标赛已经结束了。虽然我们的英雄瓦莱拉本人并没有出席这一壮观的活动，只是在电视上观看了比赛，但这让他非常兴奋，他决定报名参加一个冬季两项赛部分。
当然，铁人两项作为任何一项运动，在实践中都证明是非常困难的。这需要很多时间和努力。锻炼，锻炼，和锻炼，-这是等待瓦莱拉的方式，他在冬季两项运动的伟大成就。
至于训练，你们可能都知道，每个专业的冬季两项运动员都应该快速滑雪，并在射击场精确射击。只有在这种情况下，你才能希望成功，因为跑步和射击是两个主要组成部分的冬季两项。瓦莱拉在滑雪训练中一直很努力，这也是他跑得很快的原因，但是他的射门准确度却没有什么值得称道的。
在瓦莱拉准备参加比赛的两项基础上，有一个巨大的步枪射程，有n个目标。每个目标都有一个圆的形状，每个圆的中心都位于Ox轴上。在上一次训练中，瓦莱拉总共投了m球。为了让他更容易地监控自己的结果，一位相当有名的程序员（当然是你）被委托编写一个程序，该程序将显示瓦莱拉击中了多少目标。更具体地说，对于每个目标，程序必须打印第一次成功射击的次数（在目标中），如果没有击中，则打印−1。如果射击在圆圈内或其边界上，则视为击中目标。瓦莱拉指望着你，也许，多亏了你，他总有一天会赢得国际比赛。
输入文件的第一行包含整数n(1≤n≤10^4)，这是目标数。接下来的n行包含目标的描述。每个目标都是一个圆，其中心位于Ox轴上。每个圆由其中心x的坐标和半径r(1≤r≤1000)给出。可以保证两个目标不会重合、相交或相互嵌套，但它们可以相互接触。
下一行包含整数m(1≤m≤2×10^5)
这是拍摄的次数。接下来的m行包含快照的描述，快照是平面上的点，由坐标xx和yy给出(−2×10^4≤x,y≤2×10^4)
输入的所有数字都是整数。
目标和射击按输入顺序从一开始编号。
在第一行打印一个数字，瓦莱拉击中的目标数。在第二行为每个目标打印第一次击中的数字，如果不存在该数字，则打印“-1”（不带引号）。用空格分隔数字。
这道题读懂的话会发现这道题有点模拟题的意思，但是数据范围比较大所以要用二分优化
代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e4 + 10;
struct T{
int u;
int v;
int r;
int id;
int ans;
} a[N];
bool cmp(T A, T B){
return A.u < B.u;
}
bool check(int x, int y, int u, int v, int r){
return (x - u) * (x - u) + (y - v) * (y - v) <= r * r;
}
bool cmp1(T A, T B){
return A.id < B.id;
}
int n, m;
int main()
{
cin >> n;
for(int i = 1, x, y;i <= n;i ++){
cin >> x >> y;
a[i].u = x, a[i].v = 0, a[i].r = y, a[i].ans = -1, a[i].id = i;
}
sort(a + 1, a + n + 1, cmp);
cin >> m;
int sum = 0;
for(int i = 1,x,y;i <= m;i ++){
cin >> x >> y;
int l = 1, r = n;
while(l < r){
int mid = l + r >> 1;
if(a[mid].u >= x) r = mid;
else l = mid + 1;
}
for(int j = -1;j <= 1;j ++){
int idx = l + j;
if(check(x, y, a[idx].u, a[idx].v, a[idx].r) && a[idx].ans == -1){
a[idx].ans = i;
sum ++;
}
}
}
sort(a + 1, a + n + 1, cmp1);
cout << sum << endl;
for(int i = 1;i <= n;i ++) cout << a[i].ans << " ";
return 0;
}加油