在
“我们的胜利:TopCoder Open 2019”的脚步声中,
我从Algorithm轨道发布了任务
(经典体育编程。一个半小时,您需要解决Java,C#,C ++或Python中的三个问题。)1.六个派
问题陈述时间限制为4秒。
你有馅饼。 从上面看,蛋糕具有(严格)凸多边形的形状。 您将获得以整数X和Y表示的顶点坐标。
你有五个朋友。 您想将蛋糕分成相等面积的六块(但形状不一定相同)。 当然,任何人都可以做到五次削减,但只有专业人士才能做到三次削减。
找到一条直线上的三个切口,将蛋糕分成六个相等大小的块。 打印{x,y,d1,d2,d3},其中(x,y)是所有三个截面的公共点,而d1,d2,d3是弧度的截面方向角。
定义类别:CakeForSix
方法:切
参数:int [],int []
返回:double []
方法签名:double [] cut(int [] x,int [] y)
(确保您的方法是公开的)
注意事项- 沿x轴的正方向为0(弧度),沿y轴的正方向为pi / 2(弧度)。
- 对于任何整数k,方向d上的切口与pi * k + d方向上的切口相似。
- 您可以输出任何方向,它们不必来自[0,pi)。
- 分级者将计算您的六块蛋糕的面积成倍增加。 如果它们之间的相对或绝对差小于10 ^(-4),则将接受答案。
- 更准确地说,让X和Y为平地机计算的六个区域中的最小和最大。 如果Y <max(X + 10 ^(-4),X * 1 + 10 ^(-4))),那么您的答案将被接受。
- (在问题的原始版本中,使用精度1e-7代替了1e-4。为解决此问题,在存档中解决了精度限制,这是由于存在呼叫案例,很有可能使任务无法以精度1e-7求解。在理想情况下,限制不允许这种情况,但仍需要很高的精度,因此用一些常规的数值优化方法解决问题并不容易。)
局限性- x包含3到50个元素(含3和50)。
- y包含与x一样多的元素。
- 所有介于0和10,000之间的坐标
- x和y沿逆时针方向定义凸多边形。
英文原件问题陈述
时间限制为4秒。
你有蛋糕。 从上面看,蛋糕是一个(严格的)凸多边形。 在int [] sx和y中会得到其顶点的坐标。
你有五个朋友。 现在,您想将蛋糕切成六块相等的面积(但形状不一定相等)。 当然,任何人都可以做到五次削减-但是只有真正的专业人士才能做到三分!
找到穿过同一点的三个直线切口,将蛋糕切成六个相等的大部分。 返回{x,y,d1,d2,d3},其中(x,y)是三个切口的公共点,而d1,d2,d3是其弧度方向。
定义
类别:CakeForSix
方法:切
参数:int [],int []
返回:double []
方法签名:double [] cut(int [] x,int [] y)
(确保您的方法是公开的)
注意事项
-沿x轴的正方向为0(弧度),沿y轴的正方向为pi / 2(弧度)。
-对于任何整数k,沿d方向的切割都与pi * k + d方向的切割相同。
-您可以返回任何方向,它们不一定来自[0,pi)。
-分级机将计算您的六个蛋糕块的面积成倍增加。 如果它们之间的相对或绝对差小于10 ^(-4),则将接受答案。
-更准确地说,根据平地机的计算,将X和Y设为六个区域中的最小和最大区域。 然后,如果Y <max(X + 10 ^(-4),X *(1 + 10 ^(-4))),您的答案将被接受。
-(该问题的原始版本使用1e-7精度而不是1e-4。为了解决此问题,由于存在挑战案例,因此降低了精度极限,这些挑战案例很可能使任务无法以1e-7精度解决在理想的世界中,约束将不允许出现这种情况,并且仍然需要很高的精度,因此通过一些常规的数值优化来解决问题并不容易。)
约束条件
-x将包含3到50个元素(含3和50)。
-y将具有与x相同数量的元素。
-所有座标都在0到10,000之间(含0和10,000)。
-x和y将按逆时针顺序描述凸多边形。
例子
0){0,20,30,50,30,20}
{10,0,0,10,20,20}
返回值:
{24.999999999437453、9.999999999500002、0.0、0.7266423406817211、2.4149503129080787}
对称但不规则的六角形。 答案的示例对应于将其水平切成两半,并在中心进行另外两个切割,将每个部分分为三部分。
1){0,1000,0}
{0,0,1000}
返回值:
{333.3333333331763、333.3333333332546、0.7853981633986264、2.0344439357948154、2.6779450445891753}
直角三角形 同样,我们可以从沿对称轴的三个切口之一开始。
2){40,70,90,90,50}
{30,20,40,100,60}
返回值:
{69.79517771922892,52.77575974637605,2.0616329654335885,3.637826104091601,4.32123485812475}
错误的五边形。
3){300,400,300,200}
{500,600,700,600}
返回:{299.99999999974995,599.9999999995,0.0,1.107148717794088,2.034443935795705}
正方形旋转45度。

[
来源 ]