​Problem - 2180D - Codeforces​

Problem - 2180D - Codeforces

题意很简单 要求圆的面积没有交点 然后求尽可能大的相切点的个数

首先每个点的半径的上界就是他到相邻两个节点的距离的最小值

对于一段合法的圆 我们可以求一下第一个圆的半径的范围 然后就可以根据圆之间的距离求出下一个圆的半径的范围 如果最大半径大于最小半径 就是合法反之就是不合法 那么就直接分隔开 ans--

然后再分割点重复操作即可：

代码如下：

#include <bits/stdc++.h> using namespace std; #define int long long const int N=2e6+5,INF=1e18; int a[N]; void solve(){ int n; cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } if(n==1){ cout<<0<<'\n';return ; } vector<int>x(n+1,INF); for(int i=2;i<=n;i++){ int d=a[i]-a[i-1]; x[i]=min(x[i],d); x[i-1]=min(x[i-1],d); } int l=0,r=x[1]; int ans=n-1; for(int i=2;i<=n;i++){ int d=a[i]-a[i-1]; int l1=l,r1=r; l1=max(d-r,0LL); r1=min(d-l,x[i]); l=l1,r=r1; if(l>=r){ ans--; l=0;r=x[i]; } } cout<<ans<<'\n'; } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin>>t; while(t--)solve(); return 0; }