Source Code

Problem: 2839  User: JiaJunpeng 
Memory: 4228K  Time: 5860MS 
Language: C++  Result: Accepted 

Source Code 
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<stdio.h>
using namespace std;
int id,n,m,top,num[3];
double S,S1,S2,S3,xx,yy,eps=1e-7,pi=acos(-1.00),x,y,oox=100000000.00,ooy=123456789.000;
struct point
{
    double x,y;
    int id1,id2;
    bool operator <(const point &temp)const
    {
       if(abs((y-yy)*(temp.x-xx)-(x-xx)*(temp.y-yy))<eps)
          return abs(x-xx)+abs(y-yy)<abs(temp.x-xx)+abs(temp.y-yy);
       return (y-yy)*(temp.x-xx)-(x-xx)*(temp.y-yy)<0;
    }
};
point poly[100001],stack[100001],tri[3],list[10][2];
bool out[10];
struct segment
{
    int l,r;
    double area;
};
segment tree[1000000];
int inter(double x1,double y1,double x2,double y2,double x3,double y3,double x4,double y4)
{
     double ru1,ru2,A,B;
     A=(y2-y1)*(x4-x3)-(x2-x1)*(y4-y3);
     B=(y3-y1)*(x4-x3)-(x3-x1)*(y4-y3);
     if(fabs(A)<eps) 
        return 0;
     ru1=B/A;
     B=(y3-y1)*(x2-x1)-(x3-x1)*(y2-y1);
     ru2=B/A;
     x=x1+ru1*(x2-x1);
     y=y1+ru1*(y2-y1);
     if(((x<x1+eps&&x>x2-eps)||(x<x2+eps&&x>x1-eps))&&((y<y1+eps&&y>y2-eps)||(y<y2+eps&&y>y1-eps)))
     {
          if(((x<x3+eps&&x>x4-eps)||(x<x4+eps&&x>x3-eps))&&((y<y3+eps&&y>y4-eps)||(y<y4+eps&&y>y3-eps)))
              return 2;
          return 1;
     }
     return 0;
}
double cross(double x1,double y1,double x2,double y2)
{
       return x1*y2-x2*y1;
}
double comarea(double x1,double y1,double x2,double y2,double x3,double y3)
{
       return fabs((y2-y1)*x3-(x2-x1)*y3+x2*y1-x1*y2)/2.0;
}
double dist(double x1,double y1,double x2,double y2)
{
       return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
double comarg(double x,double y)
{
       double res,l=sqrt(x*x+y*y);
       res=asin(y/l);
       if(x==0)
       {
          if(y>0) 
            return pi/2;
          else
            return 3*pi/2;
       }
       if(y==0)
       {
           if(x>0)
              return 0.00;
           else 
              return pi;
       }
       if(x<=0&&y>=0)
          res=pi-res;
       else if(x<=0&&y<=0)
          res=pi-res;
       else if(x>=0&&y<=0)
          res+=2*pi;
       return res;
}
void build(int left,int right,int id)
{
     int mid=(left+right)>>1,l=2*id+1,r=2*id+2,id1,id2,id3,id4;
     double value;
     tree[id].l=left;
     tree[id].r=right;
     if(left==right)
     {
         tree[id].area=0.00;
         return;
     }
     build(left,mid,l);
     build(mid+1,right,r);
     id1=left%n;
     id2=mid%n;
     id3=(mid+1)%n;
     id4=right%n;
     value=comarea(stack[id1].x,stack[id1].y,stack[id2].x,stack[id2].y,stack[id3].x,stack[id3].y)+comarea(stack[id1].x,stack[id1].y,stack[id3].x,stack[id3].y,stack[id4].x,stack[id4].y);
     tree[id].area=tree[l].area+tree[r].area+value;
}
double query(int left,int right,int id)
{
       int id1,id2,id3,id4,l=2*id+1,r=2*id+2;
       double res; 
       if(tree[id].l==left&&tree[id].r==right)
           return tree[id].area;
       if(tree[l].r<left)
           return query(left,right,r);
       else if(tree[r].l>right) 
           return query(left,right,l);
       else
       {
           double v1=query(left,tree[l].r,l),v2=query(tree[r].l,right,r);
           res=v1+v2;
           id1=left%n;
           id2=tree[l].r%n;
           id3=tree[r].l%n;
           id4=right%n;
           res+=comarea(stack[id1].x,stack[id1].y,stack[id2].x,stack[id2].y,stack[id3].x,stack[id3].y);
           res+=comarea(stack[id3].x,stack[id3].y,stack[id4].x,stack[id4].y,stack[id1].x,stack[id1].y);
           return res;
       }
}
int findinter(int id,double x1,double y1,double x2,double y2)
{
     int idd,i,s,p,q,id1,id2,id3,id4,left,right,mid,ip1,ip2,ip,res=0,value;
     double l,in,arg,arg1,arg2,dx,dy;
     left=0;
     right=n-1;
     l=dist(x1,y1,x2,y2);
     dx=x2-x1;
     dy=y2-y1;
     arg=comarg(dx,dy);
     while(left<right-1)
     {
        mid=(left+right)>>1;
        id1=mid%n;
        id2=(mid+1)%n;
        if(comarg(stack[id2].x-stack[id1].x,stack[id2].y-stack[id1].y)<=arg)
           left=mid;
        else 
           right=mid-1;
     }
     id1=right%n;
     id2=(right+1)%n;
     if(comarg(stack[id2].x-stack[id1].x,stack[id2].y-stack[id1].y)<=arg)
         left=right;
     else
     {
         id1=left%n;
         id2=(left+1)%n;
         if(comarg(stack[id2].x-stack[id1].x,stack[id2].y-stack[id1].y)>arg)
            left=(left+n-1)%n;
     }
     ip1=(left+1)%n;
     dx=-dx;
     dy=-dy;
     arg=comarg(dx,dy);
     left=0;
     right=n-1;
     while(left<right-1)
     {
        mid=(left+right)>>1;
        id1=mid%n;
        id2=(mid+1)%n;
        if(comarg(stack[id2].x-stack[id1].x,stack[id2].y-stack[id1].y)<=arg)
            left=mid;
        else 
            right=mid-1;
     }
     id1=right%n;
     id2=(right+1)%n;
     if(comarg(stack[id2].x-stack[id1].x,stack[id2].y-stack[id1].y)<=arg)
         left=right;
     else
     {
         id1=left%n;
         id2=(left+1)%n;
         if(comarg(stack[id2].x-stack[id1].x,stack[id2].y-stack[id1].y)>arg)
            left=(left+n-1)%n;
     }
     ip2=(left+1)%n;
     if(inter(stack[ip1].x,stack[ip1].y,stack[ip2].x,stack[ip2].y,x1,y1,x2,y2)>0)
     {
         if(fabs(cross(stack[ip1].x-x1,stack[ip1].y-y1,x2-x1,y2-y1))<eps||fabs(cross(stack[ip2].x-x1,stack[ip2].y-y1,x2-x1,y2-y1))<eps)
         {
             if(id<3)
             {
                out[id]=true;
                out[(id+1)%3]=true;
             }
             return 0;
         }
          left=ip1;
          right=ip2;
          while(left>right)
             right+=n;
          ip=right%n;
          while(left<right-1)
          {
             mid=(left+right)>>1;
             idd=mid%n;
             if(cross(stack[idd].x-x,stack[idd].y-y,x2-x1,y2-y1)*cross(stack[ip].x-x,stack[ip].y-y,x2-x1,y2-y1)<eps)
                 left=mid;
             else
                 right=mid-1;
          }
          idd=right%n;
          if(cross(stack[idd].x-x,stack[idd].y-y,x2-x1,y2-y1)*cross(stack[ip].x-x,stack[ip].y-y,x2-x1,y2-y1)<eps)
               left=right;  
          id1=left%n;
          id2=(left+1)%n;
          value=inter(stack[id1].x,stack[id1].y,stack[id2].x,stack[id2].y,x1,y1,x2,y2);
          if(value==2)
             res++;
          list[id][1].x=x;
          list[id][1].y=y;
          list[id][1].id1=id1;
          list[id][1].id2=id2;
          left=ip2;
          right=ip1;
          while(left>right)
             right+=n;
          ip=right%n;
          while(left<right-1)
          {
              mid=(left+right)>>1;
              idd=mid%n;
              if(cross(stack[idd].x-x,stack[idd].y-y,x1-x2,y1-y2)*cross(stack[ip].x-x,stack[ip].y-y,x1-x2,y1-y2)<eps)
                 left=mid;
              else
                 right=mid-1;  
          }
          idd=right%n;
          if(cross(stack[idd].x-x,stack[idd].y-y,x1-x2,y1-y2)*cross(stack[ip].x-x,stack[ip].y-y,x1-x2,y1-y2)<eps)
             left=right; 
          id1=left%n;
          id2=(left+1)%n;
          value=inter(stack[id1].x,stack[id1].y,stack[id2].x,stack[id2].y,x1,y1,x2,y2);
           if(value==2)
              res++;
           list[id][0].x=x;
           list[id][0].y=y;
           list[id][0].id1=id1;
           list[id][0].id2=id2;
     }
     return res;
}
double com(int id1,int id2)
{
       double res;
       id1%=n;
       id2%=n;
       if(id1>id2)
           res=query(id1,n,0)+query(0,id2,0)+comarea(stack[id1].x,stack[id1].y,stack[id2].x,stack[id2].y,stack[0].x,stack[0].y);
       else
           res=query(id1,id2,0);
       return res;
}
int main()
{
    int i,j,s,p,q,id1,id2,id3,id4,left,right,mid,ip1,ip2,value;
    double l,in,arg,arg1,arg2,dx,dy;
    scanf("%d",&n);
     in=1000000000;
    for(i=0;i<n;i++)
    {
       scanf("%lf%lf",&poly[i].x,&poly[i].y);
       if(in>poly[i].y)
       {
          in=poly[i].y;
          id=i;
       }
    }
    swap(poly[id],poly[0]);
    xx=poly[0].x;
    yy=poly[0].y;
    sort(poly+1,poly+n);
    stack[0]=poly[0];
    stack[1]=poly[1];
    top=2;
    for(i=2;i<n;i++)
    {
        while(top>=2&&(stack[top-1].y-stack[top-2].y)*(poly[i].x-stack[top-2].x)>(stack[top-1].x-stack[top-2].x)*(poly[i].y-stack[top-2].y)-eps)
           top--;
        stack[top++]=poly[i];
    }
    n=top; 
    build(0,n,0);
    scanf("%d",&m);
    for(i=0;i<m;i++)
    {
       double ans;
       for(j=0;j<3;j++)
          scanf("%lf%lf",&tri[j].x,&tri[j].y);
       while(tri[0].x==tri[1].x&&tri[0].y==tri[1].y);
       while(tri[0].x==tri[2].x&&tri[0].y==tri[2].y);
       while(tri[1].x==tri[2].x&&tri[1].y==tri[2].y);
       xx=tri[0].x;
       yy=tri[0].y;
       sort(tri+1,tri+3);
       memset(out,false,sizeof(out));
       for(j=0;j<3;j++)
       { 
         num[j]=findinter(j,tri[j].x,tri[j].y,tri[(j+1)%3].x,tri[(j+1)%3].y);
         value=findinter(4,tri[j].x,tri[j].y,oox,ooy);
         if(value%2==0)
             out[j]=true;
       }
       for(j=0;j<3;j++)
       {
           if(out[j]==false||num[j]>0) 
              break;
       }
       S=comarea(tri[0].x,tri[0].y,tri[1].x,tri[1].y,tri[2].x,tri[2].y);
       x=(stack[0].x+stack[1].x)/2.00;
       y=(stack[0].y+stack[1].y)/2.00;
       S1=comarea(tri[0].x,tri[0].y,tri[1].x,tri[1].y,x,y);
       S2=comarea(tri[1].x,tri[1].y,tri[2].x,tri[2].y,x,y);
       S3=comarea(tri[2].x,tri[2].y,tri[0].x,tri[0].y,x,y);
       if(j>=3&&fabs(S-S1-S2-S3)>eps)
          puts("0");
       else
       {
           ans=tree[0].area;  
           for(j=0;j<3;j++)
           {  
              id1=list[j][0].id2;
              id2=list[j][1].id1;
              if(((!out[j]||!out[(j+1)%3])||num[j]>1)&&list[j][0].id1!=list[j][1].id1)
              {                                     
                 ans-=com(id1,id2);
                 ans-=comarea(list[j][0].x,list[j][0].y,stack[id1].x,stack[id1].y,list[j][1].x,list[j][1].y);
                 ans-=comarea(stack[id1].x,stack[id1].y,stack[id2].x,stack[id2].y,list[j][1].x,list[j][1].y);
              }
              if(!out[j])
              {
                  id1=j;
                  id2=(j+2)%3;
                  if(list[id1][0].id1!=list[id2][1].id1)
                  {
                    ip1=list[id1][0].id2;
                    ip2=list[id2][1].id1;
                    ans+=com(ip1,ip2);
                    ans+=comarea(list[id1][0].x,list[id1][0].y,stack[ip1].x,stack[ip1].y,stack[ip2].x,stack[ip2].y);
                    ans+=comarea(stack[ip2].x,stack[ip2].y,list[id2][1].x,list[id2][1].y,list[id1][0].x,list[id1][0].y);
                  }
                  ans+=comarea(tri[j].x,tri[j].y,list[id1][0].x,list[id1][0].y,list[id2][1].x,list[id2][1].y);
              }
           }
           printf("%.0lf\n",ans+eps);      
       }
    }
    return 0;
}

• 请看一下这组数据 (148) applepi 2011-12-21 17:22:17