Advertisement
ekzolot

Untitled

Oct 23rd, 2023
649
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.82 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. #define double long double
  4. using namespace std;
  5. double eps=1e-9;
  6. struct Point{
  7.     int x;
  8.     int y;
  9. };
  10. struct Circle{
  11.     Point o;
  12.     int r;
  13. };
  14. double distance_between_points(Point p, Point q){
  15.     return sqrt((p.x-q.x)*(p.x-q.x)+(p.y-q.y)*(p.y-q.y));
  16. }
  17. bool less_than(double a, int b){
  18.     if (a<b-eps){
  19.         return true;
  20.     }
  21.     return false;
  22. }
  23. bool equal(double a, int b){
  24.     return (abs(a-b)<eps);
  25. }
  26. bool ok(Circle omega, Point p){
  27.     return (less_than(distance_between_points(p, omega.o), omega.r) || equal(distance_between_points(p, omega.o), omega.r));
  28. }
  29. int bin(vector<int>& start, int t){
  30.     int n = (int) start.size();
  31.     int l=-1;
  32.     int r=n;
  33.     while(r-l>1){
  34.         int m=(r+l)/2;
  35.         if (start[m]<=t){
  36.             l=m;
  37.         }else{
  38.             r=m;
  39.         }
  40.     }
  41.     return l;
  42. }
  43. signed main(){
  44.     int n;
  45.     cin>>n;
  46.     vector<Circle> m(n);
  47.     vector<int> start(n);
  48.     for (int i=0; i<n; i++){
  49.         cin>>m[i].o.x>>m[i].r;
  50.         m[i].o.y=0;
  51.         start[i]=m[i].o.x-m[i].r;
  52.     }
  53.     int t;
  54.     cin>>t;
  55.     vector<int> answer(n, -1);
  56.     for (int i=0; i<t; i++){
  57.         Point p;
  58.         cin>>p.x>>p.y;
  59.         int pr=bin(start, p.x);
  60.         if (pr==-1){
  61.             continue;
  62.         }
  63.         if (ok(m[pr], p)){
  64.             if (answer[pr]==-1){
  65.                 answer[pr]=i+1;
  66.             }
  67.         }
  68.         if (p.x==start[pr] && pr>=1){
  69.             if (ok(m[pr-1], p)){
  70.                 if (answer[pr-1]==-1){
  71.                     answer[pr-1]=i+1;
  72.                 }
  73.             }
  74.         }
  75.     }
  76.     int cnt=0;
  77.     for (int i=0; i<n; i++){
  78.         if (answer[i]>0){
  79.             cnt++;
  80.         }
  81.     }
  82.     cout<<cnt<<"\n";
  83.     for (int i=0; i<n; i++){
  84.         cout<<answer[i]<<" ";
  85.     }
  86. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement