题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3982
题目意思:有一块半径为r的圆形蛋糕,其中心在原点,有一个人在某一个点(x,y),
现把蛋糕按两点所在直线切蛋糕,求切了n次后,这个人所在蛋糕的面积占总面积的百分比。
很容易想到先进行半平面交求出这个人所在位置的区域,再根据这个区域(多边形)求与圆的交,就是就个人得到的蛋糕。
代码如下:
//140MS
#include<iostream>
#include<cstdio>
#include<math.h>
#define eps 1e-8
#define maxn 10000
#define PI acos(-1.0)
struct point{double x,y;};
point p[maxn],save[maxn],temp[maxn];
point points[maxn][2];
point cen,people;
int n,ns,m;
double r;
double xmult(point p1,point p2,point p0)
{
return (p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x);
}
double dmult(point p1,point p2,point p0)
{
return (p1.x-p0.x)*(p2.x-p0.x)+(p1.y-p0.y)*(p2.y-p0.y);
}
double distance(point p1,point p2)
{
return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
void mycopy(point *s,int &ns,point *temp,int n)
{
int i;
ns=n;
for(i=0;i<n;i++)s[i]=temp[i];
}
void getline(point p1,point p2,double &a,double &b,double &c)
{
a=p2.y-p1.y;
b=p1.x-p2.x;
c=p2.x*p1.y-p1.x*p2.y;
}
point intersection(point p1,point p2,point p3,point p4)
{
point ret=p1;
double t=((p1.x-p3.x)*(p3.y-p4.y)-(p1.y-p3.y)*(p3.x-p4.x))
/((p1.x-p2.x)*(p3.y-p4.y)-(p1.y-p2.y)*(p3.x-p4.x));
ret.x+=(p2.x-p1.x)*t;
ret.y+=(p2.y-p1.y)*t;
return ret;
}
void cut(point side)
{
int i,j;
temp[0].x=-10000;temp[0].y=-10000;
temp[1].x=-10000;temp[1].y=10000;
temp[2].x=10000;temp[2].y=10000;
temp[3].x=10000;temp[3].y=-10000;
ns=m=4;
for(i=0;i<n;i++)
{
double a,b,c;
if(xmult(side,points[i][1],points[i][0])>=0)
getline(points[i][0],points[i][1],a,b,c);
else getline(points[i][1],points[i][0],a,b,c);
int cnt=0;
for(j=0;j<ns;j++)
{
if(a* temp[j].x+b* temp[j].y+c>=0)
{
save[cnt++]=temp[j];
}
else
{
point p1=temp[(j-1+ns)%ns],p2=temp[(j+1)%ns];
if(a*p1.x+b*p1.y+c>0)
save[cnt++]=intersection(points[i][0],points[i][1],p1,temp[j]);
if(a*p2.x+b*p2.y+c>0)
save[cnt++]=intersection(points[i][0],points[i][1],p2,temp[j]);
}
}
mycopy(temp,ns,save,cnt);
}
}
double cirtri(point pa,point pb,point po,double r)
{
double a,b,c,x,y;
double area=xmult(pa,pb,po)/2;
a=distance(po,pb);
b=distance(po,pa);
c=distance(pa,pb);
if(a<=r&&b<=r)//1
{
return area;
}
else if(a<r&&b>=r)//2
{
x=(dmult(pa,po,pb)+sqrt(c*c*r*r-xmult(pa,po,pb)*xmult(pa,po,pb)))/c;
return asin(area*(c-x)*2/c/b/r)*r*r/2+area*x/c;
}
else if(a>=r&&b<r)//3
{
y=(dmult(pb,po,pa)+sqrt(c*c*r*r-xmult(pb,po,pa)*xmult(pb,po,pa)))/c;
return asin(area*(c-y)*2/c/a/r)*r*r/2+area*y/c;
}
else if(fabs(2*area)>=r*c||dmult(pb,po,pa)<=0
||dmult(pa,po,pb)<=0)//4
{
if(dmult(pa,pb,po)<0)
{
if(xmult(pa,pb,po)<0)
{
return (-PI-asin(area*2/a/b))*r*r/2;
}
else return (PI-asin(area*2/a/b))*r*r/2;
}
else return asin(area*2/a/b)*r*r/2;
}
else //5
{
x=(dmult(pa,po,pb)+sqrt(c*c*r*r-xmult(pa,po,pb)*xmult(pa,po,pb)))/c;
y=(dmult(pb,po,pa)+sqrt(c*c*r*r-xmult(pb,po,pa)*xmult(pb,po,pa)))/c;
return (asin(area*(1-x/c)*2/r/b)
+asin(area*(1-y/c)*2/r/a))*r*r/2
+area*((y+x)/c-1);
}
}
int main()
{
int cas;
scanf("%d",&cas);
int i,j,k;
for(k=1;k<=cas;k++)
{
scanf("%lf%d",&r,&n);
for(i=0;i<n;i++)
scanf("%lf%lf%lf%lf",&points[i][0].x,&points[i][0].y,
&points[i][1].x,&points[i][1].y);
scanf("%lf%lf",&people.x,&people.y);
cut(people);
double res=0;
cen.x=0;cen.y=0;
for(i=0;i<ns;i++)
res+=cirtri(save[i],save[(i+1)%ns],cen,r);
double ans=fabs(100.0*res)/(PI*r*r);
printf("Case %d: %.5lf%%\n",k,ans);
}
return 0;
}
分享到:
相关推荐
标题中的"hdu5102.zip_K."暗示这是一个与编程竞赛相关的题目,通常在HDU(杭州电子科技大学)在线判题系统中出现。这个题目可能是一个编程挑战,要求参赛者解决一个特定的问题,并提交源代码以供自动评判。"K."可能...
【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...
《杭电OnlineJudge 2000-2099解题报告》是针对杭州电子科技大学(HDU)在线评测系统(OnlineJudge)中2000至2099题目的详细解答集锦,主要涵盖了算法分析、编程技巧以及问题解决策略等内容。这份解题报告以CHM...
杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU...
2.18.1 HDU4656 卷积取模 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 2.19 其它公式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 2.19.1 Polya . . . ....
解题报告|ACM|程序设计参考程序以及题目的分析
HDU操作系统实验.zip大学期间操作系统实验-HDU操作系统实验.zip大学期间操作系统实验-HDU操作系统实验.zip大学期间操作系统实验-HDU操作系统实验.zip大学期间操作系统实验-HDU操作系统实验.zip大学期间操作系统实验-...
【HDU-GO v19.1225.2.zip】是一个针对杭州电子科技大学(HDU)选课系统的浏览器插件,版本号为v19.1225.2。这个插件的主要功能是优化和提升学生在进行网络选课时的体验,它可能包含了增强界面、自动化操作、数据解析...
- 定义状态$Area = height[i] * (j - k + 1)$,其中$j$和$k$分别为左右边界。 - 计算左右边界时,可以使用两次单调递减栈,分别从左到右和从右到左扫描数组。 #### CityGame 题目链接:[CityGame]...
HDU(杭州电子科技大学在线评测系统)是一个深受程序员喜爱的在线编程练习平台,它提供了丰富的算法题目供用户挑战,帮助他们提升编程技能和算法理解能力。"hdu.rar_hdu"这个压缩包文件很可能是某位程序员整理的他在...
【标题】"hdu_acm_1084.rar_ACM_HDU10_acm10_hdu_hdu 1084" 提供的是一个关于杭电(HDU)ACM竞赛第1084题的解决方案。该题目可能是在编程竞赛中常见的算法问题,而ACM(国际大学生程序设计竞赛)是全球知名的编程...
【标题】"HDU-2000-2099.zip_hdu2000" 是一个包含杭电(Hangzhou Dianzi University)ACM竞赛题目解题报告的压缩包,覆盖了编号从2000到2099的题目。这个资源对于学习算法、提高编程技巧以及准备ACM/ICPC(国际大学...
本资源为HDU数字图像处理课程 浙江省在线平台的视频课后作业 仅供参考 假设我们有一个mat型的单通道图像,命名为srcMat,我们想得到第i行,第j列的像素值则可以用一下的代码 A. int value= srcMat.at(i)(j)[0]; B...
【标题】"HDU.rar_hdu_hdu07_com_shownv9b_www.563hdu." 暗示这是一个与HDU(杭州电子科技大学在线编程平台)相关的压缩包,其中可能包含了该平台上的编程竞赛题目或练习题目的源代码。"hdu07"可能是某个特定题目的...
【标签】"hdu" 表明这是与杭州电子科技大学(HDU)相关的内容,通常在ACM竞赛圈子中,大学会举办在线判题系统(如HDU OJ),供参赛者提交代码并测试其正确性。这些标签有助于分类和查找特定学校的练习题目和解决方案...
【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...
ACM HDU 题目分类 ACM HDU 题目分类是指对 HDU 在线判题系统中题目的分类,总结了大约十来个分类。这些分类将有助于编程选手更好地理解和解决问题。 DP 问题 DP(Dynamic Programming,动态规划)是一种非常重要...