盒子里的气球-Linux大棚

admin 管理员组

文章数量: 1087649

盒子里的气球

盒子里的气球（World Finals 2002 Balloons in a Box)

附下福州大学的oj上的链接 .php?pid=1515

#include<stdio.h> #include<string.h> #include<math.h> #include<stdlib.h> #include<algorithm> using namespace std; const int maxn = 10; struct point {int x, y, z; }; struct balloon {int x, y, z;int d_wall;double r;}; balloon b[maxn]; point box0, box1; int idx[maxn]; bool vis[maxn]; int n; double v; double ans; const double pi = acos(-1.0); const double inf = 10000000000.0; double volume() {return fabs((double)(box1.x-box0.x) * (box1.y-box0.y) * (box1.z-box0.z)); } double dist(int idx1, int idx2) {return sqrt((double)(b[idx1].x-b[idx2].x)*(b[idx1].x-b[idx2].x)+ (double)(b[idx1].y-b[idx2].y)*(b[idx1].y-b[idx2].y)+ (double)(b[idx1].z-b[idx2].z)*(b[idx1].z-b[idx2].z)); } void dfs(int step, double vol) {if(step == n){ // printf("%.2lf %.2lf/n", v, vol);if(ans > v - vol)ans = v-vol;return ;}else{for(int i = 0; i < n; i++)if(!vis[i]){vis[i] = true;double r = b[i].d_wall; // printf("%.2lf/n", r);for(int j = 0; j < n; j++)if(i != j && vis[j])r = min(r, dist(i, j)-b[j].r);b[i].r = r; // printf("%.2lf/n", b[i].r);if(r > 0)dfs(step+1, vol + 4.0*pi*r*r*r/3);elsedfs(step+1, vol);vis[i] = false;}} } #define LOCAL int main() { #ifdef LOCAL freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endifwhile(scanf("%d", &n) == 1){scanf("%d%d%d", &box0.x, &box0.y, &box0.z);scanf("%d%d%d", &box1.x, &box1.y, &box1.z);// printf("%.2lf %.2lf %.2lf/n", box0.x, box0.y, box0.z); // printf("%.2lf %.2lf %.2lf/n", box1.x, box1.y, box1.z);for(int i = 0; i < n; i++){scanf("%d%d%d", &b[i].x, &b[i].y, &b[i].z);b[i].d_wall = min(abs(box0.x-b[i].x), abs(box1.x-b[i].x));b[i].d_wall = min(b[i].d_wall, abs(box0.y-b[i].y));b[i].d_wall = min(b[i].d_wall, abs(box1.y-b[i].y));b[i].d_wall = min(b[i].d_wall, abs(box0.z-b[i].z));b[i].d_wall = min(b[i].d_wall, abs(box1.z-b[i].z));b[i].r = 0;idx[i] = i;}v = volume();ans = inf; // printf("%.2lf/n", v);memset(vis, false, sizeof(vis));dfs(0, 0.0);printf("%.lf/n", ans);} }

本文标签：盒子里的气球

版权声明：本文标题：盒子里的气球内容由网友自发贡献，该文观点仅代表作者本人，转载请联系作者并注明出处：http://www.roclinux.cn/b/1687331013a90377.html，本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。

更多相关文章

Linux大棚 – 不忘初心的技术博客，浮躁时代的安静角落

盒子里的气球

盒子里的气球

更多相关文章

盒子里的气球

发表评论

推荐文章

simics - Where can I access additional examples of DML devices? - Stack Overflow

javascript - Code splitting not happening via React lazy import ,and Webpack - Stack Overflow

javascript - Postman console log not allowing to write string in next line - Stack Overflow

win10开机自启动项目在哪关闭

windows通过iscsi挂载linux硬盘

热门文章

Delaying Javascript - Stack Overflow

javascript - show different keyboard character from the typed one in google chrome - Stack Overflow

javascript - Why doesn't the component tag in Vue3 work properly for dynamically rendering components? - Stack Overflow

优盘弹出文件或目录损坏且无法读取实测解决教程

javascript - Load more table rows on scroll down - Stack Overflow

c# - Unity 6, Scriptable Object Event System Doesn't Work After Restarting Unity editor - Stack Overflow

How perform sql like query (may be matcher?) on custom properties in python object? - Stack Overflow

javascript - Save HTML5 video currentTime before user leaves or closes page - Stack Overflow

javascript - Fetch request to http address from a https website - Stack Overflow

w ndows7怎么设置打印机,windows7中如何设置打印机纸张大小以241-2纸张为例

最新文章

javascript - How do I toggle the readonly attribute of all child element with jquery - Stack Overflow

javascript - Might it be possible to block an entire US state from accessing my site, using PHP? - Stack Overflow

c++ - Is dereferencing std::span::end always undefined? - Stack Overflow

javascript - Delay function execution if it has been called recently - Stack Overflow

javascript - Google Maps Autocomplete List - Stack Overflow

Windows系统更新，显示Windows启动管理器，进去后为重装系统界面的解决方法。

win11登录密码忘记了？别慌！无需重装系统，一个U盘轻松移除！

ThinkBook 16p笔记本系统重装全流程指南

openstack(train)创建网络与虚拟机

Java实现SNMP网络设备MIB信息采集系统设计与源代码分析

Exploring the Finest Accommodations: A Comprehensive Guide to Ruston LA Hotels

The Enchanting Experience of ScaliniTella NYC: A Culinary Gem in the Heart of Manhattan

Exploring the Exquisite Aloft Chicago O'Hare: A Blend of Modern Luxury and Convenience

A Culinary Journey: Discovering the Finest Dining Experiences in Waco, TX

A Culinary Journey: Discovering the Finest Dining Experiences in Athens, GA

Linux大棚 – 不忘初心的技术博客，浮躁时代的安静角落

盒子里的气球

盒子里的气球

更多相关文章

盒子里的气球

发表评论

推荐文章

simics - Where can I access additional examples of DML devices? - Stack Overflow

javascript - Code splitting not happening via React lazy import ,and Webpack - Stack Overflow

javascript - Postman console log not allowing to write string in next line - Stack Overflow

win10开机自启动项目在哪关闭

windows通过iscsi挂载linux硬盘

热门文章

Delaying Javascript - Stack Overflow

javascript - show different keyboard character from the typed one in google chrome - Stack Overflow

javascript - Why doesn&#39;t the component tag in Vue3 work properly for dynamically rendering components? - Stack Overflow

优盘弹出文件或目录损坏且无法读取实测解决教程

javascript - Load more table rows on scroll down - Stack Overflow

c# - Unity 6, Scriptable Object Event System Doesn&#39;t Work After Restarting Unity editor - Stack Overflow

How perform sql like query (may be matcher?) on custom properties in python object? - Stack Overflow

javascript - Save HTML5 video currentTime before user leaves or closes page - Stack Overflow

javascript - Fetch request to http address from a https website - Stack Overflow

w ndows7怎么设置打印机,windows7中如何设置打印机纸张大小 以241-2纸张为例

最新文章

javascript - How do I toggle the readonly attribute of all child element with jquery - Stack Overflow

javascript - Might it be possible to block an entire US state from accessing my site, using PHP? - Stack Overflow

c++ - Is dereferencing std::span::end always undefined? - Stack Overflow

javascript - Delay function execution if it has been called recently - Stack Overflow

javascript - Google Maps Autocomplete List - Stack Overflow

Windows系统更新，显示Windows启动管理器，进去后为重装系统界面的解决方法。

win11登录密码忘记了？别慌！无需重装系统，一个U盘轻松移除！

ThinkBook 16p笔记本系统重装全流程指南

openstack(train)创建网络与虚拟机

Java实现SNMP网络设备MIB信息采集系统设计与源代码分析

Exploring the Finest Accommodations: A Comprehensive Guide to Ruston LA Hotels

The Enchanting Experience of ScaliniTella NYC: A Culinary Gem in the Heart of Manhattan

Exploring the Exquisite Aloft Chicago O'Hare: A Blend of Modern Luxury and Convenience

A Culinary Journey: Discovering the Finest Dining Experiences in Waco, TX

A Culinary Journey: Discovering the Finest Dining Experiences in Athens, GA

javascript - Why doesn't the component tag in Vue3 work properly for dynamically rendering components? - Stack Overflow

c# - Unity 6, Scriptable Object Event System Doesn't Work After Restarting Unity editor - Stack Overflow

w ndows7怎么设置打印机,windows7中如何设置打印机纸张大小以241-2纸张为例