首页 > 代码库 > POJ3675 Telescope 圆和多边形的交
POJ3675 Telescope 圆和多边形的交
POJ3675
用三角剖分可以轻松搞定,数据也小 随便AC。
#include<iostream> #include<stdio.h> #include<stdlib.h> #include<string.h> #include<math.h> #include<algorithm> #include<queue> #include<vector> using namespace std; const double eps=1e-10,PI=acos(-1.0); int cmp(double k) { return k<-eps ? -1:k>eps ? 1:0; } const double pi=acos(-1.0); inline double sqr(double x) { return x*x; } struct point { double x,y; point (){} point (double a,double b):x(a),y(b){} bool input() { return scanf("%lf%lf",&x,&y)!=EOF; } friend point operator +(const point &a,const point &b) { return point(a.x+b.x,a.y+b.y); } friend point operator -(const point &a,const point &b) { return point(a.x-b.x,a.y-b.y); } friend bool operator ==(const point &a,const point &b) { return cmp(a.x-b.x)==0&&cmp(a.y-b.y)==0; } friend point operator *(const point &a,const double &b) { return point(a.x*b,a.y*b); } friend point operator*(const double &a,const point &b) { return point(a*b.x,a*b.y); } friend point operator /(const point &a,const double &b) { return point(a.x/b,a.y/b); } double norm() { return sqr(x)+sqr(y); } }; double mysqrt(double x) { return sqrt(x); } double dot(const point &a,const point &b) { return a.x*b.x+a.y*b.y; } double cross(const point &a,const point &b) { return a.x*b.y-a.y*b.x; } double abs(const point &o) { return sqrt(dot(o,o)); } void circle_cross_line(point a,point b,point o,double r,point ret[],int &num) { double x0=o.x,y0=o.y; double x1=a.x,y1=a.y; double x2=b.x,y2=b.y; double dx=x2-x1,dy=y2-y1; double A=dx*dx+dy*dy; double B=2*dx*(x1-x0)+2*dy*(y1-y0); double C=sqr(x1-x0)+sqr(y1-y0)-sqr(r); double delta=B*B-4*A*C; num=0; if(cmp(delta)>=0) { double t1=(-B-mysqrt(delta))/(2*A); double t2=(-B+mysqrt(delta))/(2*A); if(cmp(t1-1)<=0&&cmp(t1)>=0) { ret[num++]=point(x1+t1*dx,y1+t1*dy); } if(cmp(t2-1)<=0&&cmp(t2)>=0) { ret[num++]=point(x1+t2*dx,y1+t2*dy); } } } point crosspt(const point &a,const point &b,const point &p,const point &q) { double a1=cross(b-a,p-a); double a2=cross(b-a,q-a); return (p*a2-q*a1)/(a2-a1); } double sector_area(const point &a,const point &b,const double r) { double theta=atan2(a.y,a.x)-atan2(b.y,b.x); while(cmp(theta)<=0)theta+=2*PI; while(cmp(theta-2*PI)>0)theta-=2*PI; theta=min(theta,2*PI-theta); return r*r*theta/2.; } double calc_c(const point &a,const point &b,const double r) { point p[2]; int num=0; bool ina=cmp(abs(a)-r)<0; bool inb=cmp(abs(b)-r)<0; if(ina) { if(inb)return fabs(cross(a,b))/2.; else { circle_cross_line(a,b,point(0,0),r,p,num); return fabs(sector_area(b,p[0],r))+fabs(cross(a,p[0]))/2.; } } else { if(inb) { circle_cross_line(a,b,point(0,0),r,p,num); return fabs(sector_area(p[0],a,r))+fabs(cross(p[0],b))/2.; } else { circle_cross_line(a,b,point(0,0),r,p,num); if(num==2) { return fabs(sector_area(a,p[0],r))+fabs(sector_area(p[1],b,r))+fabs(cross(p[0],p[1]))/2.; }else { return fabs(sector_area(a,b,r)); } } } } double area(int n,point res[],double r) { double ret=0.; for(int i=0;i<n;i++) { int sgn=cmp(cross(res[i],res[(i+1)%n])); if(sgn!=0) { ret+=sgn*calc_c(res[i],res[(i+1)%n],r); } } return ret; } point pp[100]; int main() {freopen("t.txt","r",stdin); double r; int n; while(scanf("%lf",&r)!=EOF) { scanf("%d",&n); for(int i=0;i<n;i++) pp[i].input(); pp[n]=pp[0]; printf("%.2f\n",fabs(area(n,pp,r))+eps); } return 0; }
POJ3675 Telescope 圆和多边形的交
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。