#P9827. [ICPC 2020 Shanghai R] Sky Garden

    ID: 11057 远端评测题 1000ms 1024MiB 尝试: 0 已通过: 0 难度: 4 上传者: 标签>动态规划 DP数学2020上海Special JudgeO2优化ICPC

[ICPC 2020 Shanghai R] Sky Garden

题目描述

Prof. Du and Prof. Pang plan to build a sky garden near the city of Allin. In the garden, there will be a plant maze consisting of straight and circular roads.

On the blueprint of the plant maze, Prof. Du draws nn circles indicating the circular roads. All of them have center (0,0)(0, 0). The radius of the ii-th circle is ii.

Meanwhile, Prof. Pang draws mm lines on the blueprint indicating the straight roads. All of the lines pass through (0,0)(0, 0). Each circle is divided into 2m2m parts with equal lengths by these lines.

Let QQ be the set of the n+mn+m roads. Let PP be the set of all intersections of two different roads in QQ. Note that each circular road and each straight road have two intersections.

For two different points aPa\in P and bPb\in P, we define dis({a,b})dis(\{a, b\}) to be the shortest distance one needs to walk from aa to bb along the roads. Please calculate the sum of dis({a,b})dis(\{a, b\}) for all {a,b}P\{a, b\}\subseteq P.

输入格式

The only line contains two integers n,m (1n,m500)n,m~(1\le n,m\le 500).

输出格式

Output one number -- the sum of the distances between every pair of points in PP.

Your answer is considered correct if its absolute or relative error does not exceed 10610^{-6}.

1 2
14.2831853072
2 3
175.4159265359

提示

$dis(p_1, p_2)=dis(p_2, p_3)=dis(p_3, p_4)=dis(p_1, p_4)=\frac{\pi}{2}$

$dis(p_1, p_5)=dis(p_2, p_5)=dis(p_3, p_5)=dis(p_4, p_5)=1$

dis(p1,p3)=dis(p2,p4)=2dis(p_1, p_3)=dis(p_2, p_4)=2