栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

poj 3947 Top Spinning

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

poj 3947 Top Spinning

#include<iostream>#include<cstdlib>#include<cstring>#include<algorithm>#include<cmath>#include<stdio.h>using namespace std;double fenzi[2],fenmu,S,x,y,eps=1e-7,arg,delta,X,Y,pi=acos(-1.00),ansx,ansy,oox=1412.000,ooy=3756.000;struct pp{   char flag[11];   double x,y,r,arg,x0,y0;};pp aa[111];int n,cnt;double area(double x1,double y1,double x2,double y2,double x3,double y3){     return ((x2-x1)*(y3-y1)-(y2-y1)*(x3-x1))/2.00;}void G(double x1,double y1,double x2,double y2,double x3,double y3){      x=(x1+x2+x3)/3.00;      y=(y1+y2+y3)/3.00;}bool inter(double x1,double y1,double x2,double y2,double x3,double y3,double x4,double y4){     double a1,b1,c1,a2,b2,c2;     a1=y2-y1;     b1=x1-x2;     c1=y1*x2-y2*x1;     a2=y4-y3;     b2=x3-x4;     c2=y3*x4-y4*x3;     if(a1*b2==a2*b1)        return false;     x=(c2*b1-c1*b2)/(a1*b2-a2*b1);     y=(c2*a1-c1*a2)/(b1*a2-b2*a1);     if(!((x<x1+eps&&x>x2-eps)||(x<x2+eps&&x>x1-eps)))         return false;     if(!((y<y1+eps&&y>y2-eps)||(y<y2+eps&&y>y1-eps)))         return false;     if(!((x<x3+eps&&x>x4-eps)||(x<x4+eps&&x>x3-eps)))         return false;     if(!((y<y3+eps&&y>y4-eps)||(y<y4+eps&&y>y3-eps)))         return false;     return true;}int main(){    int i,j,s,p,q;    double a,b,c,A,B,C,k,arg1,arg2;    while(scanf("%s",aa[0].flag)&&strcmp(aa[0].flag,"end")!=0)    {         scanf("%lf%lf",&aa[0].x,&aa[0].y);         n=1;         while(true)         { scanf("%s",aa[n].flag); if(strcmp(aa[n].flag,"close")==0) {     if(aa[n-1].x!=aa[0].x||aa[n-1].y!=aa[0].y)     {        strcpy(aa[n].flag,"line"); aa[n].x=aa[0].x;        aa[n++].y=aa[0].y;     }     break; }         scanf("%lf%lf",&aa[n].x,&aa[n].y); if(strcmp(aa[n].flag,"arc")==0)     scanf("%lf",&aa[n].r); n++;         }         fenzi[0]=fenzi[1]=fenmu=0;         for(i=1;i<n;i++)         {  if(i+1<n)  {     S=area(aa[0].x,aa[0].y,aa[i].x,aa[i].y,aa[i+1].x,aa[i+1].y);     if(S!=0)     {        G(aa[0].x,aa[0].y,aa[i].x,aa[i].y,aa[i+1].x,aa[i+1].y);        fenzi[0]+=S*x;        fenzi[1]+=S*y;        fenmu+=S;     }  }  if(strcmp(aa[i].flag,"arc")==0)  {     a=2*(aa[i].x-aa[i-1].x);     b=2*(aa[i].y-aa[i-1].y);     c=aa[i].x*aa[i].x-aa[i-1].x*aa[i-1].x+aa[i].y*aa[i].y-aa[i-1].y*aa[i-1].y;     if(b==0)     {         x=c/a;         y=aa[i].y+sqrt(aa[i].r*aa[i].r-(x-aa[i].x)*(x-aa[i].x));         if((aa[i].r<0&&(aa[i].y-y)*(aa[i-1].x-x)<(aa[i-1].y-y)*(aa[i].x-x))||(aa[i].r>0&&(aa[i].y-y)*(aa[i-1].x-x)>(aa[i-1].y-y)*(aa[i].x-x)))         {   y=aa[i].y-sqrt(aa[i].r*aa[i].r-(x-aa[i].x)*(x-aa[i].x));   while((aa[i].y-y)*(aa[i-1].x-x)<(aa[i-1].y-y)*(aa[i].x-x));         }     }     else     {        A=a*a+b*b;        B=2*(b*aa[i].y-c)*a-2*b*b*aa[i].x;        C=b*b*aa[i].x*aa[i].x+(c-aa[i].y*b)*(c-aa[i].y*b)-aa[i].r*aa[i].r*b*b;        delta=B*B-4*A*C;        x=(-B+sqrt(delta))/(2*A);        y=(c-a*x)/b;        if((aa[i].r<0&&(aa[i].y-y)*(aa[i-1].x-x)<(aa[i-1].y-y)*(aa[i].x-x))||(aa[i].r>0&&(aa[i].y-y)*(aa[i-1].x-x)>(aa[i-1].y-y)*(aa[i].x-x)))        {   x=(-B-sqrt(delta))/(2*A);   y=(c-a*x)/b;        }     }     aa[i].x0=x;     aa[i].y0=y;     X=(aa[i].x+aa[i-1].x)/2.0;     Y=(aa[i].y+aa[i-1].y)/2.0;     arg=sqrt((aa[i].x-X)*(aa[i].x-X)+(aa[i].y-Y)*(aa[i].y-Y))/abs(aa[i].r);     arg=2*asin(arg);     aa[i].arg=arg;     S=aa[i].r*aa[i].r*(arg-sin(arg))/2.00;     if(aa[i].r>0)        S=-S;     double val=sin(arg/2.00);     double len1=2.0*abs(aa[i].r*aa[i].r*aa[i].r)*val*val*val/(3.0*abs(S)),len2=sqrt((aa[i].x0-X)*(aa[i].x0-X)+(aa[i].y0-Y)*(aa[i].y0-Y));     x=aa[i].x0+len1*(X-aa[i].x0)/len2;     y=aa[i].y0+len1*(Y-aa[i].y0)/len2;     fenzi[0]+=S*x;     fenzi[1]+=S*y;     fenmu+=S;  }         }         ansx=fenzi[0]/fenmu;         ansy=fenzi[1]/fenmu;         printf("%.4lf %.4lf",ansx+eps,ansy+eps);         cnt=0;         for(i=1;i<n;i++)         {  if(strcmp(aa[i].flag,"line")==0)      cnt+=inter(ansx,ansy,oox,ooy,aa[i-1].x,aa[i-1].y,aa[i].x,aa[i].y);  else if(strcmp(aa[i].flag,"arc")==0)  {      k=(ansy-ooy)/(ansx-oox);      b=(ansy*oox-ooy*ansx)/(oox-ansx);      A=1+k*k;      B=2*(b-aa[i].y0)*k-2*aa[i].x0;      C=aa[i].x0*aa[i].x0+(b-aa[i].y0)*(b-aa[i].y0)-aa[i].r*aa[i].r;      delta=B*B-4*A*C;      if(delta>=0)      {x=(-B+sqrt(delta))/(2*A);y=k*x+b;if((x<oox+eps&&x>ansx-eps)){    arg=aa[i].arg;    arg1=(x-aa[i].x0)*(aa[i-1].x-aa[i].x0)+(y-aa[i].y0)*(aa[i-1].y-aa[i].y0);    arg1/=(aa[i].r*aa[i].r);    arg1=acos(arg1);    arg2=(x-aa[i].x0)*(aa[i].x-aa[i].x0)+(y-aa[i].y0)*(aa[i].y-aa[i].y0);    arg2/=(aa[i].r*aa[i].r);    arg2=acos(arg2);    if(abs(arg1+arg2-arg)<eps)        cnt++;}x=(-B-sqrt(delta))/(2*A);y=k*x+b;if((x<oox+eps&&x>ansx-eps)){    arg=aa[i].arg;    arg1=(x-aa[i].x0)*(aa[i-1].x-aa[i].x0)+(y-aa[i].y0)*(aa[i-1].y-aa[i].y0);    arg1/=(aa[i].r*aa[i].r);    arg1=acos(arg1);    arg2=(x-aa[i].x0)*(aa[i].x-aa[i].x0)+(y-aa[i].y0)*(aa[i].y-aa[i].y0);    arg2/=(aa[i].r*aa[i].r);    arg2=acos(arg2);    if(abs(arg1+arg2-arg)<eps)        cnt++;}      }  }         }          if(cnt%2==0)printf(" -n");         elseprintf(" +n");    }    return 0;}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/377239.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号