# Poj Solution 1813

```http://poj.org/problem?id=1813

#include<iostream>
#include"math.h"
#include"stdio.h"
using namespace std;

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("%.0fn",(x2-x1)*(y2-y1));
else printf("0n");
}
else if(c1=='C'&&c2=='C'){if(p1.x==p3.x&&p1.y==p3.y){r=r1<r2?r1:r2;printf("%.0fn",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("0n");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("%.0fn",area);
}

else            {if(c1=='C')printf("%.0fn",doit(p3,p4,p1,r1));
else printf("%.0fn",doit(p1,p2,p3,r2));
}

}
return 0;
}
```
This entry was posted in poj. Bookmark the permalink.