[BSOI 1156]半平面交

【题目大意】

给出N个凸多边形（坐标按逆时针给出），让你求面积交。

【其它】1A

194906 edward_mj 1156 Accepted 184K 15MS G++ 1.73K 2010-02-15 17:53:10

【CODE】

#include #include struct point{double x,y;};
struct line{double a,b,c;};
point p[1000000],pt[1000000],pre,now,st,O;
int n,tot;

void init(){
     O.x=0; O.y=0;
     scanf("%d%d",&tot,&n);
     for (int i=1;i<=n;i++)
         scanf("%lf%lf",&p[i].x,&p[i].y);
}

double X(point p0,point p1,point p2){
       return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}

line getline(point p1,point p2){
     line New;
     New.a=p1.y-p2.y;
     New.b=p2.x-p1.x;
     New.c=X(p1,p2,O);
     return New;
}

point jiaodian(point p1,point p2,point p3,point p4){
      point New;
      line l1=getline(p1,p2),l2=getline(p3,p4);
      double tmp=l1.a*l2.b-l2.a*l1.b;
      New.x=(l1.b*l2.c-l2.b*l1.c)/tmp;
      New.y=-(l1.a*l2.c-l2.a*l1.c)/tmp;
      return New;
}

void cut(){
     int N=0;
     p[n+1]=p[1];
     for (int i=2;i<=n+1;i++)
       if (X(pre,now,p[i-1])<0){
            if (X(pre,now,p[i])>0)
              pt[++N]=jiaodian(pre,now,p[i-1],p[i]);
       }
       else{
            pt[++N]=p[i-1];
            if (X(pre,now,p[i])<0)
              pt[++N]=jiaodian(pre,now,p[i-1],p[i]);
       }
     for (int i=1;i<=N;i++) p[i]=pt[i];
     n=N;
}

void work(){
     int m;
     for (int i=1;i       scanf("%d",&m);
       scanf("%lf%lf",&st.x,&st.y);
       pre=st;
       for (int i=1;i           scanf("%lf%lf",&now.x,&now.y);
           cut();
           pre=now;
       }
       now=st;
       cut();
     }
}

void print(){
     p[n+1]=p[1];
     double ans=0;
     for (int i=1;i<=n;i++)
       ans+=(p[i].x*p[i+1].y-p[i+1].x*p[i].y)/2;
     ans=fabs(ans);
     printf("%.3lfn",ans);
}

int main(){
    init();
    work();
    print();
}