UVa 10240 The n-Dimensional Cities

题目描述在nnn维空间中最多可以有(n1)(n1)(n1)个点两两等距。Talisman\texttt{Talisman}Talisman国的nnn维生物建造了(n1)(n1)(n1)座城市这些城市两两等距。Talisman\texttt{Talisman}Talisman的道路按照如下规则修建111. 每一座城市都可通过道路到达其他任何城市图连通。222. 一条道路段只连接两个不同的城市。333. 两个城市之间最多只有一条直接道路段无重边。444. 任意城市的任意两个邻居之间都没有直接道路相连。若两座城市AAA和BBB之间有直接道路段则称它们为邻居。若AAA的两个邻居是BBB和CCC则BBB和CCC永远不会是邻居。该条件等价于图中不存在三角形。555. 连接两个相邻城市的道路段要么是直线要么是圆弧。圆弧道路段实际是一个圆的一部分该圆的圆心到两座城市的距离均为ddd英里。这里满足d≥0.5×d \ge 0.5 \timesd≥0.5×两城市的直线距离。Talisman\texttt{Talisman}Talisman中最多50%50\%50%的道路为圆弧且圆弧道路的数量永远不会超过直线道路的数量。666. 可假设任意两条道路段不相交。通信部长希望修建尽可能多的道路段在满足所有约束的前提下自然部长希望道路的总长度尽可能长他在道路两侧种树。给定Talisman\texttt{Talisman}Talisman的描述你需要求出道路段的数量以及道路的总长度。输入格式输入文件包含若干行每行有三个整数dim世界维度正整数小于100001000010000dist任意两城市间的直线距离0dist≤100000 dist \le 100000dist≤10000d圆心到城市的距离dist2.0≤d10000\frac{dist}{2.0} \le d 100002.0dist​≤d10000。输入以EOF\texttt{EOF}EOF结束。输出格式对于每一行输入输出一行包含两个整数四舍五入第一个数道路段的最大数量第二个数最大总长度实际总长度四舍五入到最接近的整数。样例输入2 10 10 3 5 6输出2 20 4 20题目分析1. 城市数量与图模型城市数为Vdim1V dim 1Vdim1。城市之间的道路关系构成一个简单无向图顶点代表城市边代表道路段。约束条件444要求任意两个邻居之间没有边即图中不存在三角形triangle-free\texttt{triangle-free}triangle-free。同时图必须连通规则111。由于没有重边且无自环该图为简单图。2. 最大道路段数对于VVV个顶点的无三角形图其最大边数由极值图论中的Turaˊn\texttt{Turán}Turaˊn定理给出emax⁡⌊V24⌋ e_{\max} \left\lfloor \frac{V^2}{4} \right\rflooremax​⌊4V2​⌋该上界由完全二分图K⌊V/2⌋,⌈V/2⌉K_{\lfloor V/2 \rfloor, \lceil V/2 \rceil}K⌊V/2⌋,⌈V/2⌉​达到该图显然无三角形且连通。因此道路段的最大数量固定为E⌊(dim1)24⌋ E \left\lfloor \frac{(dim1)^2}{4} \right\rfloorE⌊4(dim1)2​⌋3. 使总长度最大对于每条可能的边道路段有两种修建方式直线或圆弧。直线长度固定为distdistdist。圆弧长度给定圆心到两端点距离均为ddd弦长为distdistdist。设圆弧对应的圆心角为θ\thetaθ则弦长公式dist2dsin⁡(θ/2)dist 2d \sin(\theta/2)dist2dsin(θ/2)故弧长sdθ2d⋅arcsin⁡(dist2d)s d\theta 2d \cdot \arcsin\left(\frac{dist}{2d}\right)sdθ2d⋅arcsin(2ddist​)。由于d≥dist2d \ge \frac{dist}{2}d≥2dist​可知arcsin⁡\arcsinarcsin的参数在[0,1][0,1][0,1]内且圆弧长度s≥dists \ge dists≥dist当d→∞d \to \inftyd→∞时s→dists \to dists→dist但始终不小于直线长度。因此自然部长希望尽量多用圆弧以增加总长度。但约束5限制圆弧道路数不超过总边数的50%50\%50%即C≤⌊E/2⌋C \le \lfloor E/2 \rfloorC≤⌊E/2⌋圆弧道路数不超过直线道路数即C≤SC \le SC≤S其中SE−CS E - CSE−C。这两个条件合并等价于C≤⌊E/2⌋C \le \lfloor E/2 \rfloorC≤⌊E/2⌋因为SE−C≥E−⌊E/2⌋⌈E/2⌉≥CS E-C \ge E - \lfloor E/2 \rfloor \lceil E/2 \rceil \ge CSE−C≥E−⌊E/2⌋⌈E/2⌉≥C故最大可行圆弧数为C⌊E/2⌋C \lfloor E/2 \rfloorC⌊E/2⌋。于是最优方案为选择CCC条边修成圆弧其余SE−CS E - CSE−C条修成直线总长度达到最大值LS⋅distC⋅s L S \cdot dist C \cdot sLS⋅distC⋅s4. 四舍五入最后将LLL四舍五入到最接近的整数。由于所有长度均为正可使用floor(L 0.5)实现四舍五入。解题思路读取输入逐行读取三个整数dim、dist、d直到文件结束。计算顶点数Vdim1V dim 1Vdim1。计算最大边数E⌊V2/4⌋E \lfloor V^2 / 4 \rfloorE⌊V2/4⌋使用整数除法(V * V) / 4即可C 整数除法自动向下取整。计算圆弧长度使用双精度浮点数s2.0×d×arcsin⁡(dist2.0×d) s 2.0 \times d \times \arcsin\left(\frac{dist}{2.0 \times d}\right)s2.0×d×arcsin(2.0×ddist​)注意参数范围合法且使用asin函数来自cmath。计算最优分配圆弧边数CE/2C E / 2CE/2整数除法向下取整直线边数SE−CS E - CSE−C。计算总长度LS×distC×s L S \times dist C \times sLS×distC×s四舍五入rounded (long long)floor(L 0.5)。输出每行输出E和rounded。复杂度分析每个测试用例仅需常数次算术运算和一次三角函数计算时间复杂度为O(1)O(1)O(1)。空间复杂度为O(1)O(1)O(1)。代码实现// The n-Dimensional Cities// UVa ID: 10240// Verdict: Accepted// Submission Date: 2026-06-20// UVa Run Time: 0.000s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){intdim,dist,d;while(cindimdistd){longlongVdim1;longlongedges(V*V)/4;// 最大边数整数除法向下取整doubleratiodist/(2.0*d);// 弦长与直径之比doublearcLen2.0*d*asin(ratio);// 单条圆弧长度longlongcircularEdgesedges/2;// 最多圆弧数longlongstraightEdgesedges-circularEdges;// 剩余为直线doubletotalLenstraightEdges*distcircularEdges*arcLen;longlongroundedLen(longlong)floor(totalLen0.5);coutedges roundedLen\n;}return0;}总结本题的关键在于将实际问题转化为图论模型并利用Turaˊn\texttt{Turán}Turaˊn直接得出最大边数避免了繁琐的组合枚举。同时圆弧长度的计算只需一次反三角函数分配策略则通过简单的整除得出最优解。该题体现了数学定理在算法设计中的强大作用同时也考察了对浮点数四舍五入的处理技巧。