SkyGarden

NC214899. SkyGarden

描述

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 ${n}$ circles indicating the circular roads. All of them have center ${(0, 0)}$ . The radius of the ${i}$ -th circle is ${i}$ .

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

Let ${Q}$ be the set of the ${n+m}$ roads. Let ${P}$ be the set of all intersections of two different roads in ${Q}$ . Note that each circular road and each straight road have two intersections.

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

输入描述

The only line contains two integers .

输出描述

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

Your answer is considered correct if its absolute or relative error does not exceed .

示例1

输入:

1 2

输出:

14.2831853072

说明:

$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(p_1, p_3)=dis(p_2, p_4)=2$

示例2

输入:

2 3

输出:

175.4159265359

上次编辑到这里，代码来自缓存点击恢复默认模板

Python3(3.9) 解法, 执行用时: 21ms, 内存消耗: 2868K, 提交时间: 2021-01-31 02:19:35

import math
n, m = map(int, input().split())
k1 = (1 + n) * n * n / 2 - n * (n + 1) * (2 * n + 1) / 6  # 这里是一个平方和
k2 = (1 + n) * n * (n + 0.5) / 2 - n * (n + 1) * (2 * n + 1) / 6
ans = (1 + n) * n * m if m != 1 else 0
ans += 4 * m * m * k1
t = math.floor(2 * m / math.pi)
ans += (2 * math.pi * t * (t + 1) + (4 * m * (m - t) - 2 * m) * 2) * k2
print(ans)

C++(clang++11) 解法, 执行用时: 8ms, 内存消耗: 380K, 提交时间: 2020-12-13 13:00:11

#include<bits/stdc++.h>
using namespace std;
double pi=acos(-1);
int n,m;double ans;
int main(){
	scanf("%d%d",&n,&m);
	if(m>1)ans=m*n*(n+1);
	for(int i=1;i<=n;++i){
		double tmp=0;
		for(int j=1;j<=2*m;++j){
			tmp+=min(min(j,2*m-j)*pi/m,2.0)*i;
		}
		
		ans+=2*m*((n-i)*(n-i+1)*m+(n-i)*tmp+tmp/2);
	}
	printf("%.10f\n",ans);
	return 0;
}