河南网站建设多少钱,如何建设备案网站视频教程,亿企搜网站建设,厦门建设局网站2018Sky Garden
题意#xff1a;
画n个圆和m条直线#xff0c;圆的中心点为(0,0)#xff0c;圆的半径分别从1到n#xff0c;而直线都必经过(0,0)点#xff0c;并且所有直线会把每个圆平均分成2m个面积相等的区域#xff0c;直线会和圆形成交点#xff0c;求所有交点两两经…Sky Garden
题意
画n个圆和m条直线圆的中心点为(0,0)圆的半径分别从1到n而直线都必经过(0,0)点并且所有直线会把每个圆平均分成2m个面积相等的区域直线会和圆形成交点求所有交点两两经过线的最短路径的和。
题解
因为题目多圆多线所以我们分类讨论 情况一对于一个圆上的两个点他们之间的最短距离是圆弧的长度或者是两者到圆心的距离和即图中的粉色和绿色部分
情况二对于不是一个圆上的两个点A和B他们之间的最短距离是从外圈圆B通过直线到内圈圆C然后C到A的最短距离 如图 具体步骤 1… 我们首先要计算中心交点到个点的距离和对于半径为i的圆上交点AA到圆心的距离为A一共n个圆距离就是1…n n * (1n)/2,然后有m条直线也就是2 * m个从原点延伸的方向每个方向都是这种情况所以答案就是 n * (1n) * m 2. 我们要按照从内圆到外圆的方式来计算每此执行都用sum来记录圆内某点到其他点其他共2 * m -1个的距离和。图一A到B的圆心距离和为iii为第i个圆半径也就是i圆弧距离为 2 * pi * i * (j/2m), 2 * pi * i 好理解就是圆的周长后面这个(j/2m)是什么意思因为圆被分为2m份有2 * m个射线j表示一侧的第j1个边我们考虑第一个线和第j1个线之间的圆弧情况。然后pi * i * j和2 * i比较大小选择即可 图中的三个绿色弧线分别表示j1,23 我们求完一侧后根据对称性另一侧也就知道了所以前两个弧*2再加上最后一段弧因为左侧只需要考虑两个点 对于第一个射线是这么考虑一共2 * m个射线 sum要乘2m 但是这样是存在重复的我们考虑第一条射线绿色和第二条射线紫色发现蓝色画圈部分是重复计算的同理其他射线也是如此。相当于绿色部分的边除了最长的那个半圆边都重复了2 * m次最长的那个半圆边重复了m次所以记得减去 完成圆内计算后就需要计算圆内各点到外层圆上各点的最短距离和我们根据情况二得到圆内某个点到达外层圆上的所有点的距离和为m * (1(n-i)) * (n-i)sum * (n-i) m * (1(n-i)) * (n-i)是当前第i层圆上某点到达外层圆上各点时走到直线上的路程图二中C到B的过程 式子是怎么得到的 从C到B再往外距离是1…n-i 求和然后乘2m就是m * (1(n-i)) * (n-i) sum * (n-i)则计算的是圆内某点到达外层圆上各点投影到当前圆上各点的距离和也就是图二中A到C的过程 最后要乘2m 这个题说简单简单说难也难。。。 好好考虑考虑
代码
#includebits/stdc.h
using namespace std;
const double pi acos(-1);int main()
{int n,m;scanf(%d %d,n,m);double ans0;if(m!1) ansans(1n)*n*m;for(int i1;in;i){double sub0;double sum0;for(int j1;jm;j){if(jm){subsubm*2*i;sumsum*22*i;}else{if((pi*i*j)/m2*i){sumsum(pi*i*j)/m;subsub2*m*((pi*i*j)/m);}else{sumsum2*i;subsub2*m*2*i;}}}anssum*2*m-sub;ansans(m*(1(n-i))*(n-i)sum*(n-i))*2*m;}printf(%.10f\n,ans);return 0;
}
