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.

Leave a Reply