Description

给定一个100*100*100(单位:毫米)的奶酪方块,这个奶酪含有n个球形小孔。现在要求将这个奶酪切成s片使得每片质量相等。

Input

第一行包含两个整数n,s,表示奶酪有n个小空,要切成s片(0≤n≤10000,1≤s≤100)

接下来n行每行包含四个正整数r,x,y,z来描述每个小孔,r代表半径,(x,y,z)代表球心坐标。0≤r,x,y,z≤100,000(单位:微米)
我们假定切割必须垂直于z轴。对于小孔,孔与孔之间不会重叠(但可能相切),且每个孔都完全被奶酪包含(可能与奶酪边界相切)。

Output

从边界z=0依次输出每片的厚度(单位:毫米),输出答案与标准答案的相对误差或绝对误差不超过1e-6。

二分答案,由于球互不相交所以体积很好算,不完整的球体积用定积分可以推出公式,完整的用球的体积公式

#include<cstdio>
#include<cmath>
typedef long double ld;
const ld pi=acos(-.);
int n,s;
ld zs[],rs[],ps[];
ld V=;
ld get(ld x){
ld a=x*;
for(int i=;i<n;i++)if(zs[i]+rs[i]<=x){
a-=rs[i]*rs[i]*rs[i]*(./.*pi);
}else if(zs[i]-rs[i]<x){
ld z=x-zs[i];
a-=./.*pi*rs[i]*rs[i]*rs[i]+pi*(rs[i]*rs[i]*z-z*z*z/.);
}
return a;
}
ld cal(ld V){
ld L=,R=,M;
while(L+1e-<R){
M=(L+R)*.;
if(get(M)<V)L=M;
else R=M;
}
return L;
}
ld cals(ld x){
ld a=;
for(int i=;i<n;i++)if(zs[i]+rs[i]>=x&&zs[i]-rs[i]<=x){
ld z=x-zs[i];
a-=pi*(rs[i]*rs[i]-z*z);
}
return a;
}
int main(){
scanf("%d%d",&n,&s);
for(int i=,x;i<n;i++){
scanf("%d",&x);
rs[i]=x*0.001;
scanf("%d",&x);
scanf("%d",&x);
scanf("%d",&x);
zs[i]=x*0.001;
V-=rs[i]*rs[i]*rs[i]*(./.*pi);
}
ps[]=;
for(int i=;i<=s;i++)ps[i]=cal(i*V/s);
for(int i=;i<=s;i++)printf("%.9Lf\n",ps[i]-ps[i-]);
return ;
}

最新文章

  1. 迁移学习( Transfer Learning )
  2. Code Contracts for .NET
  3. oracle-5-的升级步骤
  4. android 学习随笔二十九(自定义监听 )
  5. 【Linux】Shell脚本编程(一)
  6. CentOS6.6安装mysql出现的问题
  7. 动态加载js,css(项目中需要的)
  8. Windos系统git提交
  9. HashPayloadPcapReader
  10. jQuery事件控制点击内容下拉
  11. drf相关问题
  12. js数组sort排序方法的算法
  13. 第47章:MongoDB-用户管理
  14. c/c++ 数组 数组的引用,指针数组的引用
  15. redis:order set有序集合类型的操作(有序集合)
  16. 北航学堂Android客户端Beta阶段测试报告
  17. Qt QDataTime QString 两个类的使用
  18. Linq中连接
  19. AMD,CMD,UMD 三种模块规范 写法格式
  20. maven新建web项目提示The superclass &quot;javax.servlet.http.HttpServlet&quot; was not found on the Java Build Path

热门文章

  1. PAT (Basic Level) Practise:1004. 成绩排名
  2. abap程序修改程序
  3. jq事件冒泡问题
  4. 那些盒模型在IE6中的BUG们,工程狮的你可曾遇到过?
  5. mysql时间类型在iBATIS框架下的问题(原创哦)
  6. poj3553 拓扑序+排序贪心
  7. linux下的符号链接和硬链接
  8. [BZOJ 3622]已经没有什么好害怕的了
  9. Spring MVC静态资源处理——&lt;mvc:resources /&gt; ||&lt;mvc:default-servlet-handler /&gt; 转载
  10. SharePoint入门识记