Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define int long long
- #define double long double
- using namespace std;
- double eps=1e-9;
- struct Point{
- int x;
- int y;
- };
- struct Circle{
- Point o;
- int r;
- };
- double distance_between_points(Point p, Point q){
- return sqrt((p.x-q.x)*(p.x-q.x)+(p.y-q.y)*(p.y-q.y));
- }
- bool less_than(double a, int b){
- if (a<b-eps){
- return true;
- }
- return false;
- }
- bool equal(double a, int b){
- return (abs(a-b)<eps);
- }
- bool ok(Circle omega, Point p){
- return (less_than(distance_between_points(p, omega.o), omega.r) || equal(distance_between_points(p, omega.o), omega.r));
- }
- int bin(vector<int>& start, int t){
- int n = (int) start.size();
- int l=-1;
- int r=n;
- while(r-l>1){
- int m=(r+l)/2;
- if (start[m]<=t){
- l=m;
- }else{
- r=m;
- }
- }
- return l;
- }
- signed main(){
- int n;
- cin>>n;
- vector<Circle> m(n);
- vector<int> start(n);
- for (int i=0; i<n; i++){
- cin>>m[i].o.x>>m[i].r;
- m[i].o.y=0;
- start[i]=m[i].o.x-m[i].r;
- }
- int t;
- cin>>t;
- vector<int> answer(n, -1);
- for (int i=0; i<t; i++){
- Point p;
- cin>>p.x>>p.y;
- int pr=bin(start, p.x);
- if (pr==-1){
- continue;
- }
- if (ok(m[pr], p)){
- if (answer[pr]==-1){
- answer[pr]=i+1;
- }
- }
- if (p.x==start[pr] && pr>=1){
- if (ok(m[pr-1], p)){
- if (answer[pr-1]==-1){
- answer[pr-1]=i+1;
- }
- }
- }
- }
- int cnt=0;
- for (int i=0; i<n; i++){
- if (answer[i]>0){
- cnt++;
- }
- }
- cout<<cnt<<"\n";
- for (int i=0; i<n; i++){
- cout<<answer[i]<<" ";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement