注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1502][NOI2005]月下柠檬树  

2015-06-17 23:05:34|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1502: [NOI2005]月下柠檬树

Debian的输入法图标又没了……不能打英文标点蛋疼死了
顺便一提这个题也是写得比别人都麻烦+搞了一上午

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef double ld;
const double eps = 1e-5;
const int N = 500+10;
int n,m;
double h[N],r[N],h2[N],alpha;
struct Line{
double e[2],h[2];
}data[N];int ln;
ld f(ld t){
ld R=0,d,l,rad,x,hh[2],mv[2],dd;
for(int i=1;i<n;i++){
d = t - h2[i];
if(fabs(d) <= r[i]){
R = max(R,sqrt(r[i]*r[i] - d*d));
}
}
for(int i=1;i<=ln;i++){
if(t < data[i].e[0] || t > data[i].e[1])continue;
l = (t - data[i].e[0]) / (data[i].e[1]-data[i].e[0]);
R = max(R,data[i].h[0]*(1-l) + data[i].h[1]*l);
}
return R*2;
}
ld fx(ld l,ld r){
ld F[4],mid = (l+r)/2;
F[0] = f(l);
F[1] = f(mid);
F[2] = f(r);
F[3] = (r-l)*(F[0] + F[2] + 4*F[1])/6;
return F[3];
}
ld simp(ld l,ld r){
if(r-l < 1e-5)return f(l);
ld mid = (l+r)/2;
ld F[3];
F[0] = fx(l,r);
F[1] = fx(l,mid);
F[2] = fx(mid,r);
if(fabs(F[0]-F[1]-F[2]) < eps)return F[0];
return simp(l,mid) + simp(mid,r);
}
int main(){
// freopen("in.txt","r",stdin);
// freopen("p.txt","w",stdout);
int i,j;
scanf("%d%lf",&n,&alpha);
n++;
for(i=1;i<=n;i++){
scanf("%lf",&h[i]);
h[i] += h[i-1];
h2[i] = h[i] / tan(alpha);
}
h2[n+1] = h2[n];
for(i=1;i<n;i++)
scanf("%lf",&r[i]);
r[n] = 0;
ld ans;
ans = f((h2[2]+h2[3])/2);
// printf("%.2f\n",ans);
ld L=1e50,R=-1e50;
for(i=1;i<=n;i++){
L = min(L,ld(h2[i] - r[i]));
R = max(R,ld(h2[i] + r[i]));
}

for(int i=1;i<n;i++){
double dd,rad,mv[2],hh[2],x;
dd = h2[i+1] - h2[i];
if(h2[i+1]-h2[i]+r[i+1] > r[i] && h2[i+1]-h2[i]+r[i] > r[i+1]){
ln++;
if(fabs(r[i]-r[i+1]) < eps){
// if(t < h2[i] || h2[i+1] < t)continue;
data[ln].h[0]=r[i];
data[ln].h[1]=r[i+1];
data[ln].e[0]=h2[i];
data[ln].e[1]=h2[i+1];
// R = max(R,ld(r[i]));
}else if(r[i] > r[i+1]){
x = (r[i+1] * dd)/(r[i] - r[i+1]);
rad = acos(r[i]/(x+dd));
mv[0] = cos(rad) * r[i];
mv[1] = cos(rad) * r[i+1];
data[ln].e[0] = h2[i]+mv[0];
data[ln].e[1] = h2[i+1]+mv[1];
hh[0] = sin(rad)*r[i];
hh[1] = sin(rad)*r[i+1];
data[ln].h[0] = hh[0];
data[ln].h[1] = hh[1];

}else{
x = (r[i] * dd)/(r[i+1] - r[i]);
rad = acos(r[i+1]/(x+dd));
mv[0] = cos(rad) * r[i];
mv[1] = cos(rad) * r[i+1];
data[ln].e[0] = h2[i]-mv[0];
data[ln].e[1] = h2[i+1]-mv[1];
hh[0] = sin(rad)*r[i];
hh[1] = sin(rad)*r[i+1];
data[ln].h[0] = hh[0];
data[ln].h[1] = hh[1];
}
}
}

ans = 0;
ans = simp(L,R);
/*
ans += simp(L,h2[1]);
ans += simp(h2[n],R);
for(i=1;i<n;i++){
ans += simp(h2[i],h2[i+1]);

}*/
/*
double per = (R-L)/500;
printf("%f %f\n",double(L),double(R));
i=1;
for(double x=L;x<=R;x+=per,i++){
if(i == 394){
printf("%f\n",x);
printf("%.2f\n",double(f(x)));
}
}*/

// ans = simp(L,R);
// ans += M_PI * r[1]*r[1] / 2;
printf("%.2f\n",double(ans));
return 0;
}

题解:
投影(Trace On)下来之后是一堆圆形+公切线组成的梯形并
所以我们搞一个函数f(x)表示x这个位置影子竖直长度
由于函数连续所以自适应辛普森积分
算f(x)首先要枚举所有的圆看看圆上的高度
然后枚举所有公切线看公切线上高度
注意切线要预处理否则会T
我比较蛋疼分了3类讨论……
  评论这张
 
阅读(62)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017