1. 题目背景与问题分析
今天我们来拆解一道有趣的算法竞赛题目——P5864 [SEERC 2018] Broken Watch。这道题描述了一个外星人手表损坏后,三个指针自由旋转形成三角形的场景。题目要求我们计算这些三角形中包含表盘中心的数量。
1.1 问题场景还原
想象一块圆形手表,表盘直径30mm,有三个指针长度分别为A、B、C微米(1000≤A,B,C≤15000)。与人类手表不同的是,这块表有N个刻度(2≤N<2³²)而不是60个。当手表玻璃破碎后,指针可以自由旋转指向任意刻度。
我们需要计算三个指针尖端形成的三角形中,包含表盘中心的三角形数量。注意:
- 三个指针尖端不共线(即能形成有效三角形)
- 中心在三角形边上也算包含
1.2 数学建模关键点
这个问题本质上是一个几何组合问题,我们需要考虑:
- 圆形表盘坐标系:将表盘视为单位圆,中心在原点
- 指针位置表示:每个指针尖端位置可表示为(cosθ, sinθ),θ=2πk/N (k=0,1,...,N-1)
- 三角形包含圆心条件:根据几何学原理,三角形包含圆心当且仅当三个顶点的极角满足特定条件
需要模型API调用? 免费领10W Token,多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 核心算法思路
2.1 几何条件分析
经过推导(详见附录数学证明),我们发现:
- 当N为偶数时,有效三角形数量为:(N-1)(N)(N+4)/3
- 当N为奇数时,有效三角形数量为:(N-1)(N)(2N-1)/6
这个结论与指针长度无关,只与刻度数N相关。但需要考虑指针长度相同带来的对称性。
2.2 排列组合考虑
当指针长度相同时,三角形会有重复计数的情况:
- 三个指针长度都相同:只有1种排列方式
- 两个指针长度相同:有3种排列方式
- 所有指针长度不同:有6种排列方式
因此需要乘以相应的组合系数。
3. C++实现详解
3.1 代码结构与输入处理
cpp复制#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ull unsigned long long
using namespace std;
// 快速输入输出模板
template<typename
