1813.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"iostream.h"
#include"math.h"
#include"stdio.h"

struct point
{double x,y;};

const double pi=3.14159265359;

inline double cheng(point a,point b,point c)
{return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);}
inline double dcheng(point a,point b,point c)
{return (b.x-a.x)*(c.x-a.x)+(c.y-a.y)*(b.y-a.y);}

double doit(point p1,point p2,point o,double r)
{point px,p[16];int set[16];int s=0;double t;
	
 p1.x-=o.x;
 p1.y-=o.y;
 p2.x-=o.x;
 p2.y-=o.y;
 o.x=0;
 o.y=0;
 
 if(fabs(p1.y)<=r){px.x=-sqrt(r*r-p1.y*p1.y);px.y=p1.y;
				   if(fabs(p1.x)<=fabs(px.x)||fabs(p2.x)<=fabs(px.x))
				   {
				   t=px.x;
				   set[s]=0;px.x=p1.x<px.x?px.x:p1.x;p[s++]=px;
				   px.x=-t;
				   set[s]=1;px.x=p2.x>px.x?px.x:p2.x;p[s++]=px;
				   }
				}
  if(fabs(p2.x)<=r){px.y=-sqrt(r*r-p2.x*p2.x);px.x=p2.x;
				   if(fabs(p1.y)<=fabs(px.y)||fabs(p2.y)<=fabs(px.y))
				   {
				   t=px.y;
				   set[s]=0;px.y=p1.y<px.y?px.y:p1.y;p[s++]=px;
				   px.y=-t;
				   set[s]=1;px.y=p2.y>px.y?px.y:p2.y;p[s++]=px;
				   }
				}
  if(fabs(p2.y)<=r){px.x=sqrt(r*r-p2.y*p2.y);px.y=p2.y;
				   if(fabs(p1.x)<=fabs(px.x)||fabs(p2.x)<=fabs(px.x))
				   {
				   t=px.x;
				   set[s]=0;px.x=p2.x>px.x?px.x:p2.x;p[s++]=px;
				   px.x=-t;
				   set[s]=1;px.x=p1.x<px.x?px.x:p1.x;p[s++]=px;
				   }
				}
  if(fabs(p1.x)<=r){px.y=sqrt(r*r-p1.x*p1.x);px.x=p1.x;
				   if(fabs(p1.y)<=fabs(px.y)||fabs(p2.y)<=fabs(px.y))
				   {
				   t=px.y;
				   set[s]=0;px.y=p2.y>px.y?px.y:p2.y;p[s++]=px;
				   px.y=-t;
				   set[s]=1;px.y=p1.y<px.y?px.y:p1.y;p[s++]=px;
				   }
				}
 double area=0;
 for(int i=0;i<s;i++)
 {p1=p[i];p2=p[(i+1)%s];
  if(set[(i+1)%s])area+=cheng(o,p1,p2)/2;
  else {if(cheng(o,p2,p1)<0)area+=acos(dcheng(o,p1,p2)/r/r)*r*r/2;
		else if(cheng(o,p2,p1)>0)area+=(2*pi-acos(dcheng(o,p1,p2)/r/r))*r*r/2;
		}
 }

  if(!s){if(p1.x<0&&p2.x>0&&p1.y<0&&p2.y>0)return pi*r*r;
			else return 0;
		}
  return area;
 }


int main()
{point p1,p2,p3,p4;
double r1,r2,r,da,db,l,area;
int t;
double x1,x2,y1,y2;char c1,c2;
cin>>t;

while(t--)
{cin>>c1;
cin>>p1.x>>p1.y;
if(c1=='R')cin>>p2.x>>p2.y;
else cin>>r1;

cin>>c2;
cin>>p3.x>>p3.y;
if(c2=='R')cin>>p4.x>>p4.y;
else cin>>r2;

if(c1=='R'&&c2=='R'){x1=p1.x>p3.x?p1.x:p3.x;x2=p2.x>p4.x?p4.x:p2.x;
					 y1=p1.y>p3.y?p1.y:p3.y;y2=p2.y>p4.y?p4.y:p2.y;
					if(x2>x1&&y2>y1)printf("%.0f\n",(x2-x1)*(y2-y1));
				     else printf("0\n");
					}
else if(c1=='C'&&c2=='C'){if(p1.x==p3.x&&p1.y==p3.y){r=r1<r2?r1:r2;printf("%.0f\n",pi*r*r);continue;}
					 
					 l=sqrt((p1.x-p3.x)*(p1.x-p3.x)+(p1.y-p3.y)*(p1.y-p3.y));
					 if(l>=r1+r2){printf("0\n");continue;}
					 
					 da=acos((l*l+r1*r1-r2*r2)/2/l/r1);
					 db=acos((l*l+r2*r2-r1*r1)/2/l/r2);
					
					 area=r1*r1*da+r2*r2*db-r1*l*sin(da);
					  printf("%.0f\n",area);
					}
					 
else			{if(c1=='C')printf("%.0f\n",doit(p3,p4,p1,r1));
					else printf("%.0f\n",doit(p1,p2,p3,r2));
				}

}
return 0;
}