CGL_4_C : Convex Cut - sinapusu2002 @ ウィキ

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_4_C
凸多角形を直線で分割した時の直線より左側の面積を求める問題。

ショートコードを目指したわけでなく普通に実装したらコードの短さ1位を取りました。
小さな三角形に分けて面積を足したり引いたりしてます。

#include<stdio.h>
#include<algorithm>
#include<vector>
std::vector<double> xs,ys;

 
void f(){
   double xa,ya,xb,yb;
   scanf("%lf %lf %lf %lf",&xa,&ya,&xb,&yb);
   xb-=xa;
   yb-=ya;
   double ans=0;
   for(int i=0;i<xs.size();i++){
       int p1=i;
       int p2=(i+1)%xs.size();
       double x1,y1,x2,y2,g1,g2;
       x1=xs[p1]-xa;
       y1=ys[p1]-ya;
       x2=xs[p2]-xa;
       y2=ys[p2]-ya;
       g1=xb*y1-yb*x1;
       g2=xb*y2-yb*x2;
       if(g1*g2<0){
            
           double s,xd,yd,xc,yc;
           xd=x2-x1;
           yd=y2-y1;
           s=(y1*xb-x1*yb)/(yb*xd-xb*yd);
           xc=x1+xd*s;
           yc=y1+yd*s;
           if(g1>0){
               ans+=(x1*yc-y1*xc); 
           }
           if(g2>0){
               ans+=(xc*y2-yc*x2);
           }
       }else{
           if((g1<=0)&&(g2<=0)){
               ans+=0;
           }else{
               ans+=(x1*y2-x2*y1);
           }
       }
   }
   printf("%.7lf\n",ans/2.0);
}

int main(){
   int n;
   scanf("%d",&n);
   for(int i=0;i<n;i++){
       double x,y;
       scanf("%lf %lf",&x,&y);
       xs.push_back(x);
       ys.push_back(y);
   }
   int q;
   scanf("%d",&q);
   for(int i=0;i<q;i++){
       f();
   }
}