CF-1009-D. Counting Points · znzryb

## 思路讲解

其实不难，挺简单的。

我的思路是由于限制了半径的大小的总和，所以说可以把每个圆的每个x都扫一遍，扫到这个x了这个圆在这个x上包含了几个点就很容易知道了。然后把x上有多少个点被包含存在Cnt里就好了，最后扫一遍加起来就好。

```cpp
	FOR(i,1,N){
		ll r=xr[i][1],x=xr[i][0];
		FOR(j,x-r,x+r){
			ll len=abs(j-x);
			ll yCanChoose=sqrtl(r*r-len*len);
			yCanChoose*=2,yCanChoose+=1;
			if(Cnt.find(j)==Cnt.end()){
				Cnt[j]=yCanChoose;
			}else{
				Cnt[j]=max(yCanChoose,Cnt[j]);
			}
		}
	}
	ll ans=0;
	for(auto ele:Cnt){
		ans+=ele.se;
	}
```

## AC代码

[https://codeforces.com/contest/2074/submission/318915158](https://codeforces.com/contest/2074/submission/318915158)



::: 源代码

```cpp
// Problem: D. Counting Points
// Contest: Codeforces - Codeforces Round 1009 (Div. 3)
// URL: https://codeforces.com/contest/2074/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define getFro(vec) (vec.empty()?0:vec.front())
#define getBac(vec) (vec.empty()?0:vec.front())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define DEBUG(variable) \
    do { \
        std::cerr << #variable << ":"; \
        for (const auto& elem : variable) { \
            std::cerr << elem << " "; \
        } \
        std::cerr << "\n"; \
    } while (0)
#define uniVec(var) \
    do { \
        sort(var.begin(),var.end());\
        var.resize(unique(var.begin(),var.end())-var.begin());\
    } while (0)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,2> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(2e5)+10,INF=static_cast<ll>(1e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,K,T; // X[MAXN],R[MAXN];
arr xr[MAXN];
ll rToNum[MAXN];

inline void solve(){
	cin>>N>>M;
	map<ll,ll> Cnt;
	FOR(i,1,N){
		cin>>xr[i][0];
	}
	FOR(i,1,N){
		cin>>xr[i][1];
	}
	// sort(xr+1,xr+1+N);
	// ll ans=0;
	// FOR(i,1,N){
		// ll r=xr[i][1];
		// ans+=r;
	// }
	FOR(i,1,N){
		ll r=xr[i][1],x=xr[i][0];
		FOR(j,x-r,x+r){
			ll len=abs(j-x);
			ll yCanChoose=sqrtl(r*r-len*len);
			yCanChoose*=2,yCanChoose+=1;
			if(Cnt.find(j)==Cnt.end()){
				Cnt[j]=yCanChoose;
			}else{
				Cnt[j]=max(yCanChoose,Cnt[j]);
			}
		}
	}
	ll ans=0;
	for(auto ele:Cnt){
		ans+=ele.se;
	}
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	FOR(i,1,MAXN-5){
		
	}
	while(T--){
		solve();
	}
	// solve();
	return 0;
}
/*
AC
https://codeforces.com/contest/2074/submission/318915158
*/
```


:::


## 心路历程（WA，TLE，MLE……）