fork(3) download
copy 
  1.     //#pragma GCC optimize("Ofast,no-stack-protector")
  2.     //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
  3.     //#pragma GCC target("avx,tune=native")
  4.     // Anand Jaisingh
  5.  
  6.     #include<bits/stdc++.h>
  7.  
  8.     using namespace std;
  9.  
  10.     typedef complex<double> base;
  11.     typedef long double ld;
  12.     typedef long long ll;
  13.  
  14.     #define pb push_back
  15.     #define pii pair<int,int>
  16.     #define pll pair< ll , ll >
  17.     #define vi vector<int>
  18.     #define vvi vector< vi >
  19.  
  20.     const int maxn=(int)(1e3+5),zz=(int)(1e6+6);
  21.     const ll mod=(ll)(1e9+7);
  22.     int a[maxn];
  23.     ld x[maxn],y[maxn],r[maxn];
  24.     int res[zz];
  25.  
  26.     void update(ld low,ld high)
  27.     {
  28.         int xx=(int)ceil(low),yy=(int)floor(high);
  29.  
  30.         if(xx<zz)
  31.         {
  32.             res[xx]++;
  33.         }
  34.  
  35.         if(yy+1<zz)
  36.         {
  37.             res[yy+1]--;
  38.         }
  39.     }
  40.  
  41.     ld dis(ld x1,ld y1,ld x2,ld y2)
  42.     {
  43.         ld val1=(x1-x2)*(x1-x2),val2=(y1-y2)*(y1-y2);
  44.  
  45.         return sqrt(val1+val2);
  46.     }
  47.  
  48.     int main()
  49.     {
  50.         ios_base::sync_with_stdio(0);cin.tie(0);
  51.  
  52.         int n,q;cin>>n>>q;
  53.  
  54.         for(int i=0;i<n;i++)
  55.         {
  56.             cin>>x[i]>>y[i]>>r[i];
  57.         }
  58.  
  59.         for(int i=0;i<n;i++)
  60.         {
  61.             for(int j=i+1;j<n;j++)
  62.             {
  63.                 ld curr1=dis(x[i],y[i],x[j],y[j]),curr2=r[i]+r[j];
  64.  
  65.                 if(curr1>curr2)
  66.                 {
  67.                     ld min=curr1-r[i]-r[j],max=curr1+r[i]+r[j];
  68.  
  69.                     update(min,max);
  70.                 }
  71.                 else
  72.                 {
  73.                     ld now=abs(r[i]-r[j])-curr1;
  74.  
  75.                     if(now>=0)
  76.                     {
  77.                         // one inside the other...
  78.  
  79.                         ld min=now,max=curr1+r[i]+r[j];
  80.  
  81.                         update(min,max);
  82.                     }
  83.  
  84.                     else
  85.                     {
  86.                         ld min=0,max=curr1+r[i]+r[j];
  87.  
  88.                         update(min,max);
  89.                     }
  90.                 }
  91.             }
  92.         }
  93.  
  94.         for(int i=1;i<zz;i++)
  95.         {
  96.             res[i]+=res[i-1];
  97.         }
  98.  
  99.         while(q>0)
  100.         {
  101.             int k;cin>>k;
  102.  
  103.             cout<<res[k]<<endl;
  104.  
  105.             q--;
  106.         }
  107.  
  108.         return 0;
  109.     }
  110.  
Runtime error #stdin #stdout 0s 19192KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/vFXV2I
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!