P9827 [ICPC 2020 Shanghai R] Sky Garden

题目描述

杜教授和庞教授计划在 Allin 市附近建造一个空中花园。在花园中，将有一个由直路和环形路组成的植物迷宫。

在植物迷宫的蓝图上，杜教授画了 $n$ 个圆，表示环形路。所有圆的圆心都是 $(0,0)$。第 $i$ 个圆的半径是 $i$。

同时，庞教授在蓝图上画了 $m$ 条直线，表示直路。所有的直线都经过 $(0,0)$。每个圆被这些直线等分成 $2m$ 个部分。

设 $Q$ 为 $n+m$ 条道路的集合。设 $P$ 为 $Q$ 中两条不同道路的所有交点的集合。注意，每条环形路和每条直路都有两个交点。

对于两个不同的点 $a\in P$ 和 $b\in P$，我们定义 dis({a,b})dis(\{a, b\})dis({a,b}) 为沿着道路从 $a$ 到 $b$ 需要走的最短距离。请计算对于所有 {a,b}⊆P\{a, b\} \subseteq P{a,b}⊆P 的 dis({a,b})dis(\{a, b\})dis({a,b}) 的和。

输入格式

唯一一行包含两个整数 $n,m(1\le n,m\le 500)$。

输出格式

输出一个数字——$P$ 中每对点之间距离的总和。

你的答案被认为是正确的，如果其绝对误差或相对误差不超过 $10^{-6}$。

输入输出样例 #1

输入 #1

1 2

输出 #1

14.2831853072

输入输出样例 #2

输入 #2

2 3

输出 #2

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

题面翻译由 ChatGPT-4o 提供。

C++实现

#include<bits/stdc++.h>
using namespace std;
const int N=500+10;
const double pi=3.1415926535897932384626433832795;
int main(){
	double n,m,ans=0;
	cin>>n>>m;
	for (int i=1; i<=n; i++)
	{
		for (int j=i; j>=1; j--)//遍历两个圆，求出固定圆后的答案并累加。
		{
			double cnt=0;
			for (int k=1; k<m; k++)//求出离一个点与另一个圆上分别1~m-1个格的点的最短路。
			{
				cnt+=i-j+min(2.0*j,(1/(2*m)*k)*pi*j*2.0);
			}
			clog<<cnt<<endl;
			if (i==j)//如果两个圆是同一个
			{
				ans+=cnt*2*m;//会重复
				ans+=(i+j)*m;//i-j=0
			}
			else
			{
				ans+=cnt*4*m;//不会
				ans+=(i+j+i-j)*2*m;
			}
		}
		if(m!=1)
		{
			ans+=i*2*m;//到圆心
		}
	}
	cout<<fixed<<setprecision(10)<<ans;
	return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容