首页 > 其他 > 详细

【计算几何】【圆反演】hdu6158 The Designer

时间:2017-08-20 09:23:43      阅读:401      评论:0      收藏:0      [点我收藏+]

技术分享

给你内外那俩圆的半径,让你按图中标号的顺序往缝里塞n个小圆,问你小圆的总面积。

不知道圆反演的先去查一下定义。

将两个圆的切点视作反演中心,任取反演半径(比如1),将两个圆反演成两条平行直线,则那些小圆都变成相同大小啦!就很好算了,我们再将小圆通过反演算回它原来的面积即可。

技术分享

怎样求原小圆的面积呢?

技术分享

只需求得AB的长度即可。因为A’距离原点的距离我们知道,B’距离原点的距离我们也知道,OA,OB就很好求了,作个差就是AB。

(这套CCPC网络赛的题是我们学校的人出的,线下测题的时候,我的这份代码能AC的,现在我交到hdu上就TLE了,貌似加强了数据,卡了常数……?)

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const double PI=acos(-1.0);
int R1,R2,n;
double sqr(double x){
	return x*x;
}
int T;
int main(){
	//freopen("e.in","r",stdin);
	scanf("%d",&T);
	for(;T;--T){
		scanf("%d%d%d",&R1,&R2,&n);
		if(R1>R2){
			swap(R1,R2);
		}
		double r=(1.0/2.0/(double)R1-1.0/2.0/(double)R2)*0.5;
		double X=(1.0/2.0/(double)R1+1.0/2.0/(double)R2)*0.5;
		double now=0,ans=0;
		for(int i=1;i<=n;++i){
			double t=sqrt(X*X+now*now);
			ans+=sqr((1.0/(t-r)-1.0/(t+r))*0.5)*PI;
			if(i&1){
				now+=r*2.0;
			}
		}
		printf("%.5lf\n",ans);
	}
	return 0;
}

【计算几何】【圆反演】hdu6158 The Designer

原文:http://www.cnblogs.com/autsky-jadek/p/7398531.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!