钟针产生的三角形面积

问题说明：

假设我们有一个时钟，它的时针长3个单位，分针长4个单位，秒针长5个单位。时针每小时移动一次，分针每分钟移动一次，秒针每秒移动一次。
因此，恰好每秒，指针两端所定义的三角形会改变其面积。
/>
哪个是两次给定时间之间的最大面积？

输入：以hh：mm：ss格式表示的一组2个小时的小时序列。

输出：双手末端定义的最大面积，以平方单位为单位。

更全面的说明：https://jutge.org/problems/P17681_zh/statement

我的代码：

我编写了一个函数，该函数以弧度为单位的手的位置作为参数，并返回其面积（三角密集型）。

>
我的主要功能是读取用户输入的内容，并在用户输入的时间范围内每秒计算一次面积，存储最大面积并最终打印出来。

double area(double secRad, double minRad, double houRad){
    double alfaSM = atan( (5-4*cos(abs(secRad-minRad)))/(4*sin(abs(secRad-minRad))) );
    double alfaSH = atan( (5-3*cos(abs(secRad-houRad)))/(3*sin(abs(secRad-houRad))) );
    double alfaMH = atan( (4-3*cos(abs(minRad-houRad)))/(3*sin(abs(minRad-houRad))) );

    double distSM = abs(5*sin(alfaSM)+4*sin(abs(secRad-minRad)-alfaSM));
    double distSH = abs(5*sin(alfaSH)+3*sin(abs(secRad-houRad)-alfaSH));
    double distMH = abs(4*sin(alfaMH)+3*sin(abs(minRad-houRad)-alfaMH));

    double s = (distSM+distSH+distMH)/2;

    return s*(s-distSM)*(s-distSH)*(s-distMH);
}

在开始时先写下来，这样您就可以st程序：

int main(){
    char z;
    double hI,mI,sI, hF,mF,sF;
    while(cin >> hI >> z >> mI >> z >> sI >> hF >> z >> mF >> z >> sF){
        double maxArea = 0;
        for(int i = 3600*hI+60*mI+sI; i <= 3600*hF+60*mF+sF; i++){
            double cacheArea = area( 2*pi*((double)(i%60)/60) , 2*pi*(double)((i%3600)/60)/60, 2*pi*(double)((i%43200)/3600)/12);
            if(cacheArea > maxArea) maxArea = cacheArea; 
        }
        cout << fixed << setprecision(3) << sqrt(maxArea) << endl;
    }
}

我现在在哪里，还剩下什么？

上面代码的算法按预期工作，但是效率不够。在线法官抛出了超出时间限制的错误。

我设法减少了所需面积的计算，方法是假设如果时间范围超过一个小时，我们只需要检查所有第一个小时的组合，因为最大的区域将会出现，并且每小时都会再次出现（相对位置重复）。

我还实现了一个变量，用于检查指针之间是否分开时钟检查的时间小于在那一刻之前发现的最大区域中的指针间隔。如果是，程序将跳过面积计算。

这些变化似乎可以显着提高性能（从12,200个区域计算到整个12小时内大约1,500个），但是法官仍然不接受。

我似乎需要更清洁的解决方案，数学上更漂亮的一个，但我一直在努力寻找一个。

如果手的长度相等，则任何等边三角形都可以解决问题（八点钟后二十秒和另外二十三秒）。从这些配置之一开始，并尝试以增加最长的长度为代价来增加最短边的长度。

@greybeard：因为只有三点，所以您不需要调整长度。 ABC，BCA，CAB都是等价的三角形，其内在等于其镜像CBA，BAC，ACB。这是仅有的6种可能性，并且可证明彼此相等。如果我们要检查四点，那就很重要，例如ABCD和ACBD完全不同。

@greybeard：结束我的想法：由于3个臂的长度恒定，因此它们之间的最佳角度（对于最大表面积）同样恒定。结合早先的评论，几乎没有理由替换臂长（因为它们总是会产生相同的结果）。找到特定臂顺序（ABC）的最佳角度，您会自动知道任意臂顺序的结果。

哦，天哪，最长时间以来，我认为这是在代码高尔夫上进行的，而且我一直在尝试找出为什么它是特定于语言的

@Flater我不建议改变手臂的长度，而是根据问题由其尖端定义的三角形的边。（通过移动秒针，分针或两者，而不是时针。）

#1 楼

首先要做的是摆脱慢速（15-30个周期）的触发函数，并用预先计算的表替换它们。由于每只手只有60个可能的位置，因此这是一个60槽位的桌子（加上一点，因为谁打扰了边界检查，说实话？....咳嗽）。

如果您想作弊，您还可以在源代码中使用预先计算的表，但这将使IMO显得有些笨拙。

旋转对称性

让我们创建一个函数A（h，m，s）会根据小时，分钟和秒来计算面积。

如果我们看着钟面并将整个东西（包括三个钟针）旋转任意角度，则面积不会改变。因此，我们可以将时针置于“ 0”（另一只针也紧随其后）。

因此，

\ $ A（h，m，s）= A（ 0，m-5h \ mod 60，s-5h \ mod 60）\ $

因此我们可以制作一个整洁的预先计算好的表区域[分钟] [秒]，并填充3600个值，然后使用那！相对于程序的libc初始化时间而言，填充时间可忽略不计，因此我无需费心对其进行进一步优化。无论如何，这只是一堆MAC，现代cpus还是以疯狂的速度运转。

此外，每分钟最大面积的计算并存储在数组marea中。这对应于h = 0，m，s = [0..59]上的最大值，并且可以通过如上所述的旋转将其扩展到任何h：m。

计数

其余的非常简单，我们从00:01:02开始，到00:35:15结束。

首先，我们将秒数从02增加到59，直到达到00 ：02：00

然后我们增加分钟，直到达到00:35:00

然后我们再次增加秒数，直到达到最终时间。

在每一步中，我们从预先计算的表中选择面积（或每分钟预先计算的最大值），并将其与我们的运行最大值进行比较。

它非常快，因为除了几个int操作，一个float cmp外，它基本上什么也不做，并且如果编译器执行其工作，则应该有几个CMOV。根本不用去尝试...

因此，这段丑陋的代码应该可以完成任务。。

这里的重点是对评审过程进行逆向工程。对于仅几行输入，即使您使用大量慢触发的实现在现代cpu上也应该足够快，与程序init相比花费的时间可以忽略不计。

因此，如果遇到时间限制错误，这意味着输入文件必须包含许多行。

因此，预先计算的查找表非常合适。第二个，然后是分钟）会大大减少迭代次数，但确实需要每分钟表预先计算的最大面积。您可以将其作为文本包含在源代码中，但这会很la脚...因此，最好预先计算所有内容，然后翻录输入文件。

如果cin >>是程序中最慢的部分...

\ $ \ begingroup \ $
如果您愿意存储30kB的高速缓存，则最好将其放入范围最小的查询数据结构中，以实现超快的查找。
\ $ \ endgroup \ $
–Veedrac
17年5月5日在17:11

\ $ \ begingroup \ $
您的代码由于某种原因无法正常工作。我一直试图找到问题所在，终于找到了它。在秒的第一个增量的末尾，选中第一分钟时，如果分钟的末尾是60，则必须添加小时的增量。无论如何，惊人的答案，谢谢！
\ $ \ endgroup \ $
– Xavi Reyes
17年12月7日在17:10

#2 楼

这是奥斯卡的答案的附录。只需做一些数学运算即可。

让t = 0为12点，当所有指针都一致且面积为0时。我们需要根据t来计算面积。令s, m, h为相对于三角参考的秒，分钟和小时的角度。然后
$$ s = \ frac {\ pi} 2- \ frac {\ pi} {30} t \\ m = \ frac {\ pi} 2- \ frac {\ pi} {1800} t \ \ h = \ frac {\ pi} 2- \ frac {\ pi} {21600} t $$
，令S, M, H为时钟指针的长度。然后该区域为
$$ A = \ frac12 \ left | SM \ sin \ alpha + MH \ sin \ beta + HS \ sin \ gamma \ right | $$
其中
$$ \ alpha = sm，\; \ beta = mh，\; \ gamma = hs $$
因此我们有
$$ \ alpha =-\ frac {59} {60} \ cdot \ frac { \ pi} {30} t \\ \ beta =-\ frac {11} {720} \ cdot \ frac {\ pi} {30} t \\ \ gamma = \ frac {719} {720} \ cdot \ frac {\ pi} {30} t $$
其中t是一个正整数。如您所见，做一些无聊的数学有时可以减少工作所需的代码量。

P.S.这是A与t的关系图。这确实是周期性的。

#3 楼

因此，首先要看的是您的area函数。当前，此操作使用15个trig运算来计算三角形的面积（3 cos，3 atan和9 sin）。可以仅使用3个sin函数和一些其他数学操作来完成相同的操作，而这将花费更少的时间。这样做的基本思想是，如果您有一个三角形的两个边长以及它们之间的夹角，则细线管的面积就是边长的乘积除以两个边长的正弦之和的两倍，或sin(θ)*a*b/2。因此，您要做的就是找到三个三角形中每个三角形的面积，并将它们加在一起。

\ $ \ begingroup \ $
很好的答案，但是可以用更少的三角函数求值！（请参阅我的回答。）
\ $ \ endgroup \ $
–克里斯·伦戈（Cris Luengo）
17-12-5'2:59

#4 楼

避免使用using namespace std;

导入名称空间的所有名称是一种不好的习惯，当begin和size之类的名称位于全局名称空间中时，可能会引起意外。习惯使用名称空间前缀（std故意很短），或仅将所需的名称导入到最小的合理范围内。

此规则的例外情况是明确打算批量导入的名称空间，例如std::literals命名空间。

优先使用命名常量而不是预处理器宏

π的值可以声明为double-并且可以计算而不是写成：

static const double pi = 4 * std::atan(1);

面积计算

area()函数名称错误-它返回面积的平方。

类似重复的表达式很容易产生简单的错别字，很容易被忽略。

每当我看到std::atan()被除法时，就表明std::atan2()可能是真正的意思。可以通过使用任意两个边的叉积作为矢量来消除三角函数（请记住除以二以将平行四边形面积转换为三角形面积！）。

主程序

计算间隔中每一秒的三角形面积效率很低。注意问题的对称性：如果时间跨度大于48分钟，我们可以简单地返回一个预先计算的常数。对于一分钟或更长的时间跨度，我们可以找到最大的区域，方法是将秒针在分针和时针之间平分大角度并将其向小时移动，直到该区域开始减小。仅在跨度两端的部分分钟内，我们才需要回过头来计算所有面积。

通过上一段的更改，不再需要将小时，分钟和秒组成一个单一的数字，然后再次分解它们。很好，因为它很复杂而且很难理解。它也有一个错误，因为12小时为43200秒，这大于（有符号）int的要求范围。

通过将I / O与最大值计算分开来改进程序。一组开始和结束值的区域。这样就可以进行一些单元测试，而不是依赖于具有输入和输出流的整个程序测试。

\ $ \ begingroup \ $
@Veedrac：形状每隔1小时5分钟重复一次，但是具有反射对称性，这意味着我们可以在一半范围内获得整个范围。除非我的推理因时针只在整整一个小时内移动而中断。
\ $ \ endgroup \ $
– Toby Speight
2017年12月5日14:44

\ $ \ begingroup \ $
@Veedrac，我已经进行了相应的编辑。
\ $ \ endgroup \ $
– Toby Speight
17年5月5日在15:50

#5 楼

给定点A，B，C的三角形面积是矢量AB和AC叉积的一半。这些点在3D中定义，z分量为零。叉积在z轴上将仅为非零（它垂直于两个向量形成的平面）。因此，您只需要计算叉积的z分量。该z分量是两个矢量跨越的平行六面体的面积。这是几个乘法，不涉及三角函数。

您确实需要三角函数来计算手的端点的位置。仅在换手时才执行此操作。或者，您甚至可以针对所有60个可能的角度预先计算正弦和余弦。并请注意，在这些角度中，只有8个以上（第一个45度）具有唯一值，其余的值都是从这些角度平凡得出的。

\ $ \ begingroup \ $
公平地说，这并不会减少触发操作，它只是缓存它们。类似的方法也可以用于我的解决方案。可能的theta是15度的倍数，因此在此之前做一张表并查找它是非常琐碎的。
\ $ \ endgroup \ $
–奥斯卡·史密斯（Oscar Smith）
17年5月5日在6:47

\ $ \ begingroup \ $
请注意，您也可以在2D中定义矢量叉积，只是输出是一个数字。我没有真正的理由在此应用程序中将东西嵌入3D空间。
\ $ \ endgroup \ $
–亚瑟
17年5月5日在12:05

\ $ \ begingroup \ $
@OscarSmith是的，或者，当然，您是对的。
\ $ \ endgroup \ $
–克里斯·伦戈（Cris Luengo）
17年5月5日在14:53

\ $ \ begingroup \ $
@Artur：叉积是3D运算符，您可以定义2D版本，但它没有固有的含义。我们仅在概念上嵌入3D，以解释为什么两个2D向量的两个分量中的特定操作集合会产生面积。
\ $ \ endgroup \ $
–克里斯·伦戈（Cris Luengo）
17年5月5日在15:03

\ $ \ begingroup \ $
感谢您为我的回答提供帮助;）
\ $ \ endgroup \ $
– bobflux
17年5月5日在17:09

#6 楼

由于问题是对称的，因此在一个小时内，所有可能的区域都“到达”了。我能想到的一种优化方法是，只要输入时间范围超过一小时，就简单地返回[预先计算的]最大可能面积。

实际上，确保达到所有面积所需的时间不是一个小时，而是2844秒！可以使用以下代码进行演示：

double maxmax = 0;    
for(int i = 0; i <= 3600; i++)
{
    double cacheArea = area( 2*pi*((double)(i%60)/60) , 2*pi*(double)((i%3600)/60)/60, 2*pi*(double)((i%43200)/3600)/12);
    if (cacheArea > maxmax) 
        maxmax = cacheArea; 
}

for (int s = 0; s <= 23*60*60; s++)
{
    double maxArea = 0;
    for(int i = s; i <= s+2844; i++)
    {
        double cacheArea = area( 2*pi*((double)(i%60)/60) , 2*pi*(double)((i%3600)/60)/60, 2*pi*(double)((i%43200)/3600)/12);
        if (cacheArea > maxArea) 
            maxArea = cacheArea; 
    }

    if (fabs(maxArea - maxmax) > 1e-10)
        cout << fixed << setprecision(3) << sqrt(maxArea) << "   " << sqrt(maxmax) << endl;
}

\ $ \ begingroup \ $
@Veedrac：正确。尽管如此，以上代码证明，任何大于2844秒的时间段都将包含全局最大值。将其更改为较低的值并不会始终达到全局最大值。
\ $ \ endgroup \ $
– Lior Kogan
17-12-5在15:11

\ $ \ begingroup \ $
抱歉，我搞砸了。你是对的。
\ $ \ endgroup \ $
–Veedrac
17年5月5日在15:26

\ $ \ begingroup \ $
感谢您为我的回答提供帮助;）
\ $ \ endgroup \ $
– bobflux
17年5月5日在17:10

#7 楼

Lior Kogan手动显示，严格超过2844秒的任何时间跨度都会达到全局最大值。

if timespan >= 2844 seconds:
    return maximum possible area

如果时间跨度不那么长，我们可以将剩下的整个分钟的数量加上两个部分的分钟。整个分钟的最大值仅由时针和分针确定。第二只手完全转身，因此我们不依赖其价值。由于问题是旋转不变的并且是对称的，因此，这仅真正取决于小时和分钟之间的绝对差，其中只有31种可能性。这些可以缓存在一个长度为31的数组中。。您可以相当快地对它们进行全面检查，但是如果分钟缓存显示整分钟从未超过当前最大值，则可以很容易地跳过它。

for hour:minute in full_minutes(timespan):
    maximum = max(maximum, full_minute_cache[abs(minute - 5 * hour)])

在最坏的情况下，总共有118个calculate_area调用和49个数组查找，这即使使用低效的方法来计算面积也非常快。更多;对于每60小时-分钟的差异，三角形的面积有一组给定的结果。我们不想只存储所有结果，但是我们可以作弊。由于函数大部分是平滑的，因此最大值将很少。结果表明总共不超过三个最大值，不超过两个内部最大值，并且不小于一个内部最大值，并且当存在三个最大值时，至少有一个在0或59秒。看一下这个\ $ x..y \ $的小节，我们知道它的全局最大值将是严格在该范围内的内部最大值之一，或者值\ $ x \ $或\ $ y \ $。严格来说只能有两个，因此这给我们留下了四个对calculate_area的调用和一个长度为120的缓存。现在，我们的总成本减少到不超过calculate_area的八个调用，两个不完整的分钟中的每个不完整的四个，分钟的47个数组查找，一个31的double数组和120字节的数组。 47次查找可能不会比对calculate_area的8次调用慢，所以这是关于优化不再是算法的地方，以及我将让此答案保留的地方。

#8 楼

优化此问题的方面很少。

首先要认识到问题空间中存在很多冗余。通过轮换，一天中的每个小时实际上都可以通过适当的轮换映射到任何其他小时。同样地，前半个小时是第二个小时的反映。这意味着我们可以预先计算一小部分非重复计算，然后将其映射到其他时间。

第二个是那些预计算不需要考虑到您的运行时；加载它们并进行查找更加有意义。它既快速又正确，不是作弊。因此，我会尝试优化不必要的值生成方式，并将结果提交到内存中。

如果您仔细查看问题空间，我们可以做得更多。 polfosol的图在这里有很大帮助：我们可以看到清晰的，规则的局部最大值，大约每分钟一次，加上清晰的最大值，每小时一次。如果我们已经知道这些最大值，并且任何给定的时间段包含一个或多个最大值，则将最大值保证为这些值中的最大值。如果我们设法选择一个不包含任何最大值的时间段，则可以保证最大值是第一个值或最后一个值（对于2个计算而言，即时计算便宜，值得进行优化）。

这使解决方案变得异常简单：对于大于一分钟的片段，我们保证在边界内进行简单搜索即可找到最大值；在最大最大值<30的最大值中搜索不是计算密集型的。对于少于一分钟的线段，我们仍然必须检查局部最大值，如果不包含局部最大值，则对书挡值进行两次计算：保证其中一个值是不包含最大值的线段中的最大值，因为该线段必须呈“ u”形或倾斜。

有时优化正在寻找一种方法来进行最少数量的计算，而不是更快地自己进行计算。

编程黑洞网