bzoj 2178 圆的面积并 —— 辛普森积分
2024-09-01 13:26:06
题目:https://www.lydsy.com/JudgeOnline/problem.php?id=2178
先看到这篇博客:https://www.cnblogs.com/heisenberg-/p/6740654.html
好像本应算弓形面积、三角形面积之类的,但不会...于是用辛普森积分硬做...
参考了这篇博客:https://blog.csdn.net/orpinex/article/details/7311363
然而如果写成精度友好型的 asr ( *15, /15, eps/2 ),或T或RE的,不精度友好反而好了...
为什么一开始传的范围是所有圆边界的 min, max 就会WA,传 -inf, inf 就A了...
总之写的时候还是尽量稳妥一点吧...
代码如下:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef double db;
int const xn=,inf=;
db const eps=1e-;
int n;
bool tmp[xn];
struct N{int x,y,r;}c[xn];
struct S{db l,r;}seg[xn];
int rd()
{
int ret=,f=; char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=; ch=getchar();}
while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();
return f?ret:-ret;
}
int dmp(db x)
{
if(fabs(x)<eps)return ;
else if(x>eps)return ;
else return -;
}
db sqr(db x){return x*x;}
bool cmp(S a,S b){return dmp(a.l-b.l)<||(dmp(a.l-b.l)==&&dmp(a.r-b.r)<);}
bool cmp2(N a,N b){return a.r<b.r;}
db maxx(db x,db y){if(dmp(x-y)<)return y; return x;}
bool in(int a,int b){return sqr(c[a].x-c[b].x)+sqr(c[a].y-c[b].y)<=sqr(c[a].r-c[b].r);}
void init()
{
sort(c+,c+n+,cmp2);
for(int i=;i<=n;i++)
{
for(int j=i+;j<=n;j++)
if(in(i,j)){tmp[i]=; break;}
}
int tot=;
for(int i=;i<=n;i++)if(!tmp[i])c[++tot]=c[i];
n=tot;
}
db f(db x)
{
int cnt=;
for(int i=;i<=n;i++)
{
if(dmp(fabs(c[i].x-x)-c[i].r)>)continue;
db dis=sqrt(sqr(c[i].r)-sqr(x-c[i].x));
seg[++cnt].l=c[i].y-dis; seg[cnt].r=c[i].y+dis;
}
sort(seg+,seg+cnt+,cmp);
db ret=,r=-inf;
for(int i=;i<=cnt;i++)
{
if(dmp(seg[i].l-r)>)ret+=seg[i].r-seg[i].l,r=seg[i].r;
else if(dmp(seg[i].r-r)>)ret+=seg[i].r-r,r=seg[i].r;
}
return ret;
}
db simp(db l,db r){return (r-l)/*(f(l)+*f((l+r)/)+f(r));}
db asr(db l,db r,db eps,db lst)
{
db mid=(l+r)/;
db ls=simp(l,mid),rs=simp(mid,r);
if(fabs(ls+rs-lst)<=*eps)return ls+rs+(ls+rs-lst)/;
return asr(l,mid,eps/,ls)+asr(mid,r,eps/,rs);
}
db asr(db l,db r,db lst)
{
db mid=(l+r)/;
db ls=simp(l,mid),rs=simp(mid,r);
if(fabs(ls+rs-lst)<=eps)return ls+rs;
return asr(l,mid,ls)+asr(mid,r,rs);
}
int main()
{
n=rd(); int L=inf,R=-inf;
for(int i=;i<=n;i++)
c[i].x=rd(),c[i].y=rd(),c[i].r=rd(),
L=min(L,c[i].x-c[i].r),R=max(R,c[i].x+c[i].r);
init();
//printf("%.3f\n",asr(L,R,eps,simp(L,R)));
//printf("%.3f\n",asr(L,R,simp(L,R)));
printf("%.3f\n",asr(-inf,inf,simp(-inf,inf)));
//printf("%.3f\n",asr(-inf,inf,eps,simp(-inf,inf)));
return ;
}
然而这样其实会错HAHA,随便来个数据竟然就错了:
3
0 0 1
0 0 1
100 100 1
应该输出 6.283,但上面的代码以及许多题解输出都是 3.142 ...
于是换了一种写法,对每个连续段做积分,这样避免了空白区域对积分结果的影响;
而且发现求一次 f(x) 很慢,所以之前求过的尽量重复利用;
然后就T了,调了两小时...
TLE 的原因竟然是 sort 里面传了 cmp() 函数??!!!如果改成重载结构体小于号,就不T了呵呵-_-
所以还是要注意代码习惯阿。
代码如下:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef double db;
int const xn=,inf=;
db const eps=1e-;
int n,st,ed,xl[xn],xr[xn];
bool tmp[xn];
struct N{
int x,y,r;
bool operator < (const N &b) const
{return r<b.r;}
}c[xn];
struct S{
db l,r;
bool operator < (const S &b) const
{return l<b.l;}
}seg[xn];
int rd()
{
int ret=,f=; char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=; ch=getchar();}
while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();
return f?ret:-ret;
}
db sqr(db x){return x*x;}
//bool cmp(S a,S b){return a.l<b.l;}
//bool cmp2(N a,N b){return a.r<b.r;}
bool cmp3(N a,N b){return a.x-a.r<b.x-b.r;}
bool in(int a,int b){return sqr(c[a].x-c[b].x)+sqr(c[a].y-c[b].y)<=sqr(c[a].r-c[b].r);}
void init()
{
sort(c+,c+n+);//cmp2
for(int i=;i<=n;i++)
{
for(int j=i+;j<=n;j++)
if(in(i,j)){tmp[i]=; break;}
}
int tot=;
for(int i=;i<=n;i++)if(!tmp[i])c[++tot]=c[i];
n=tot;
sort(c+,c+n+,cmp3);//
}
db f(db x)
{
int cnt=;
for(int i=st;i<=ed;i++)
{
if(xl[i]>=x||xr[i]<=x)continue;
db dis=sqrt(c[i].r-sqr(x-c[i].x));//(sqr)
seg[++cnt].l=c[i].y-dis; seg[cnt].r=c[i].y+dis;
}
sort(seg+,seg+cnt+);//cmp
db ret=,r=-inf;
for(int i=,j;i<=cnt;i=j)
{
r=seg[i].r;
for(j=i+;j<=cnt&&seg[j].l<=r;j++)
if(r<seg[j].r)r=seg[j].r;
ret+=r-seg[i].l;
}
return ret;
}
db simp(db len,db fl,db fr,db fm){return len/*(fl+*fm+fr);}
db asr(db l,db r,db mid,db fl,db fr,db fm,db lst)
{
db lmid=(l+mid)/,flm=f(lmid),rmid=(mid+r)/,frm=f(rmid);
db ls=simp(mid-l,fl,fm,flm),rs=simp(r-mid,fm,fr,frm);
if(fabs(ls+rs-lst)<=eps)return ls+rs;
return asr(l,mid,lmid,fl,fm,flm,ls)+asr(mid,r,rmid,fm,fr,frm,rs);
}
int main()
{
n=rd();
for(int i=;i<=n;i++)
c[i].x=rd(),c[i].y=rd(),c[i].r=rd();
init(); db ans=;
for(int i=;i<=n;i++)
xl[i]=c[i].x-c[i].r,xr[i]=c[i].x+c[i].r,c[i].r=c[i].r*c[i].r;
for(int i=,j;i<=n;i=j)
{
int l=xl[i],r=xr[i];
for(j=i+;xl[j]<=r&&j<=n;j++)if(xr[j]>r)r=xr[j];
st=i; ed=j-; db mid=(l+r)/;
db fl=f(l),fm=f(mid),fr=f(r);
ans+=asr(l,r,mid,fl,fr,fm,simp(r-l,fl,fr,fm));
}
printf("%.3f\n",ans);
return ;
}
最新文章
- BuilderParttern(建造者模式)
- 【Linux学习】Linux下用户组、文件权限详解
- 【UOJ#67】新年的毒瘤 Tarjan 割点
- Ubuntu 安装mysql和简单操作
- sql分组(orderBy、GroupBy)获取每组前一(几)条数据
- Java集合---HashMap源码剖析
- 动态创建DataTable总结
- 解析ECC与RECC内存之间的区分
- 熬之滴水成石:最想深入了解的内容--windows内核机制(15)
- FZU 2113(数位dp)
- 理解ActivityManagerService
- Spring 回滚事务@Transactional
- 【原创】java socket 和.net socket 通讯 demo
- django 完整日志配置
- Tengine安装(阿里baba的)-Nginx
- JDK+JAVA+maven+IDEA
- 【转】assert预处理宏与预处理变量
- 如何用jQuery获得select的值
- 关于ADO.Net SqlConnection的性能优化
- 线程执行synchronized同步代码块时再次重入该锁过程中抛异常,是否会释放锁