zufe 2432 圆覆盖

zufe 2432 圆覆盖"/>

zufe 2432 圆覆盖

题目描述

题解：
找一个圆，枚举圆中的纵坐标，对于每个圆循环一次求区间的并。
代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll x[102],y[102],r[102];
ll abs1(ll k)
{if(k<0)return -k;return k;
}
int main()
{int n;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%lld%lld%lld",&x[i],&y[i],&r[i]);ll ans=0;for(ll i=y[1]+r[1];i>=y[1]-r[1];i--){ll l2=1.00*x[1]-sqrt(1.00*r[1]*r[1]-1.00*(i-y[1])*(i-y[1]));ll r2=1.00*x[1]+sqrt(1.00*r[1]*r[1]-1.00*(i-y[1])*(i-y[1]));l2-=1;r2+=1;while(r[1]*r[1]-(i-y[1])*(i-y[1])<(l2-x[1])*(l2-x[1]))l2++;//控制精度。while(r[1]*r[1]-(i-y[1])*(i-y[1])<(r2-x[1])*(r2-x[1]))r2--;bool bb=1;for(int j=2;j<=n;j++){if(i>y[j]+r[j]||i<y[j]-r[j]){bb=0;break;}ll k=abs1(i-y[j]);ll l1=1.00*x[j]-sqrt(1.00*r[j]*r[j]-1.00*k*k);ll r1=1.00*x[j]+sqrt(1.00*r[j]*r[j]-1.00*k*k);l1-=1;r1+=1;while(r[j]*r[j]-(i-y[j])*(i-y[j])<(l1-x[j])*(l1-x[j]))l1++;while(r[j]*r[j]-(i-y[j])*(i-y[j])<(r1-x[j])*(r1-x[j]))r1--;if(r1<l2||l1>r2){bb=0;break;}l2=max(l2,l1);r2=min(r2,r1);}if(bb&&r2>=l2) ans+=r2-l2+1;}printf("%lld\n",ans);return 0;
}