Simpson积分(BZOJ2178)

lrj的代码常数太大T了QAQ,改了一下。

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std; typedef double db;
const int N=;
int n,t,lm=,rm=-,v[N],q[N],x[N],y[N],r[N];
pair<db,db> b[N]; db F(db a) {
int tt=;
db re=,ls=-;
for(int i=;i<=t;i++) if(fabs(a-x[q[i]])<=r[q[i]]) {
db k=sqrt(r[q[i]]*r[q[i]]-(a-x[q[i]])*(a-x[q[i]]));
b[++tt].first=y[q[i]]-k,b[tt].second=y[q[i]]+k;
}
sort(b+,b++tt);
for(int i=;i<=tt;i++) {
if(b[i].first>ls) re+=b[i].second-b[i].first,ls=b[i].second;
else if(b[i].second>ls) re+=b[i].second-ls,ls=b[i].second;
}
return re;
}
db asr(db a,db b,db c,db A,db B,db C) {
db l=F((a+c)/),r=F((c+b)/),aa=(A+C*+B)*(b-a)/,L=(A+*l+C)*(c-a)/,R=(C+*r+B)*(b-c)/;
if(fabs(L+R-aa)<=1e-) return aa;
return asr(a,c,(a+c)/,A,C,l)+asr(c,b,(b+c)/,C,B,r);
} int main() {
scanf("%d",&n);
for(int i=;i<=n;i++) {
scanf("%d%d%d",&x[i],&y[i],&r[i]);
lm=min(lm,x[i]-r[i]),rm=max(rm,x[i]+r[i]);
}
for(int i=;i<=n;i++) if(!v[i])
for(int j=;j<=n;j++) if(i!=j&&!v[j]) {
if(sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]))+r[j]<=r[i]) v[j]=;
}
for(int i=;i<=n;i++) if(!v[i]) q[++t]=i;
printf("%.3f",asr(lm,rm,(lm+rm)/2.0,,,F((lm+rm)/2.0)));
return ;
}
上一篇:[设计模式] JavaScript 之 原型模式 : Object.create 与 prototype


下一篇:javascript原型模式理解