//题目链接:http://zuojie.3322.org:88/soj/problem.action?id=4042
题目:
Description
A travelling circus faces a tough challenge in designing the dome for its performances. The circus has
a number of shows that happen above the stage in the air under the dome. Various rigs, supports, and
anchors must be installed over the stage, but under the dome. The dome itself must rise above the center
of the stage and has a conical shape. The space under the dome must be air-conditioned, so the goal is
to design the dome that contains minimal volume.
You are given a set of n points in the space; (xi, yi, zi) for 1 <= i <= n are the coordinates of the points in
the air above the stage that must be covered by the dome. The ground is denoted by the plane z = 0,
with positive z coordinates going up. The center of the stage is on the ground at the point (0, 0, 0).
The tip of the dome must be located at some point with coordinates (0, 0, h) with h > 0. The dome
must have a conical shape that touches the ground at the circle with the center in the point (0, 0, 0) and
with the radius of r. The dome must contain or touch all the n given points. The dome must have the
minimal volume, given the above constraints.
Input
The first line of the input file contains a single integer number n (1 <= n <= 10 000) — the number of
points under the dome. The following n lines describe points with three floating point numbers xi, yi,
and zi per line — the coordinates of i-th point. All coordinates do not exceed 1000 by their absolute
value and have at most 2 digits after decimal point. All zi are positive. There is at least one point with
non-zero xi or yi.
Output
Write to the output file a single line with two floating point numbers h and r — the height and the base
radius of the dome. The numbers must be precise up to 3 digits after decimal point.
Sample Input
1
1.00 0.00 1.00
2
1.00 0.00 1.00
0.00 1.50 0.50
3
1.00 0.00 1.00
0.00 1.50 0.50
-0.50 -0.50 1.00
Sample Output
3.000 1.500
2.000 2.000
2.000 2.000
Source
NEERC2010
方法就是先把这一系列的三维坐标点进行降维。
我们可以把所有的点降为一些2维平面上的点
然后,圆锥的体积就变成了面积。这样简化了代码的复杂度
另外我们通过三分技术去寻找那个体积最小的圆锥。
这样,效率也非常高。
我的代码:
分享到:
相关推荐
SOJ题目
soj 1019 1488 1822 三题的源代码 比较复杂的动态规划题
自动探测POJ、HDU、SOJ、ZOJ水题,对于有志于刷遍各种水题的ACMer来说非常有用
sicily(soj) 1022 1064 1310 1740 1876 1934 六题的源代码(数据结构综合应用题)
sonew写的oj系统。前台使用php,数据库为mysql,后台是用qt编写的。不过,后台源码没有给出,而且大家注意使用时,php的默认全局变量必须开启,你也可以自己修改相应代码,就不用开启全局变量了
soj1103_IP判断_模式匹配.cpp
SOJ与虚假目标复合干扰下目标跟踪技术
SOP、SSOP、TSSOP、SOL、SOJ的区别
LQFP、PLCC44、QFP、SOJ、SOL、TQFP、TSOP、TSSOP等贴片集成电路的PCB封装集合
acm的一手资料,玩ACM的都知道的, 基本代码库
Altium AD09 AD17 AD19 芯片接插件各类器件PCB封装库2D+3D封装合集(2020个) SMB SMB-2 SMC SMC-2 SNT-6A SO-4 SO-4 - 2 SO-8 SO-8 - 2 ...SOJ-14 SOJ-16 ...SOJ14/300 SOJ14/350 SOJ14/400 SOJ14/450 S
DIP、PLCC、SOP、PQFP、SOJ、TQFP、TSSOP、BGA
SOJ14/400 SOJ14/450 SOJ16/300 SOJ16/350 SOJ16/400 SOJ16/450 SOJ18/300 SOJ18/350 SOJ18/400 SOJ18/450 SOJ20/300 SOJ20/350 SOJ20/400 SOJ20/450 SOJ22/300 SOJ22/350 SOJ22/400 SOJ22/450 SOJ24/300 SOJ24/350 ...
SOJ14/400 SOJ14/450 SOJ16/300 SOJ16/350 SOJ16/400 SOJ16/450 SOJ18/300 SOJ18/350 SOJ18/400 SOJ18/450 SOJ20/300 SOJ20/350 SOJ20/400 SOJ20/450 SOJ22/300 SOJ22/350 SOJ22/400 SOJ22/450 SOJ24/300 SOJ24/350 ...
SOJ14/400 SOJ14/450 SOJ16/300 SOJ16/350 SOJ16/400 SOJ16/450 SOJ18/300 SOJ18/350 SOJ18/400 SOJ18/450 SOJ20/300 SOJ20/350 SOJ20/400 SOJ20/450 SOJ22/300 SOJ22/350 SOJ22/400 SOJ22/450 SOJ24/300 SOJ24/350 ...
SOJ14/400 SOJ14/450 SOJ16/300 SOJ16/350 SOJ16/400 SOJ16/450 SOJ18/300 SOJ18/350 SOJ18/400 SOJ18/450 SOJ20/300 SOJ20/350 SOJ20/400 SOJ20/450 SOJ22/300 SOJ22/350 SOJ22/400 SOJ22/450 SOJ24/300 SOJ24/350 ...
SOJ14/400 SOJ14/450 SOJ16/300 SOJ16/350 SOJ16/400 SOJ16/450 SOJ18/300 SOJ18/350 SOJ18/400 SOJ18/450 SOJ20/300 SOJ20/350 SOJ20/400 SOJ20/450 SOJ22/300 SOJ22/350 SOJ22/400 SOJ22/450 SOJ24/300 SOJ24/350 ...
SoJ0825.github.io
SOJ14/400 SOJ14/450 SOJ16/350 SOJ16/400 SOJ16/450 SOJ18-400 SOJ18/300 SOJ18/350 SOJ18/400 SOJ18/450 SOJ20/300 SOJ20/350 SOJ20/400 SOJ20/450 SOJ22/300 SOJ22/350 SOJ22/400 SOJ22/450 SOJ24/300 SOJ24/350 ...
SOJ14/400 SOJ14/450 SOJ16/350 SOJ16/400 SOJ16/450 SOJ18-400 SOJ18/300 SOJ18/350 SOJ18/400 SOJ18/450 SOJ20/300 SOJ20/350 SOJ20/400 SOJ20/450 SOJ22/300 SOJ22/350 SOJ22/400 SOJ22/450 SOJ24/300 SOJ24/350 ...