Topcoder Member SRM485 DIV 1 1000pt

给定一个凸多边形包围住另一个凸多边形，外面的凸多边形上的每个点都向离自己的最远的在外凸多边形上的点连一条线。然后问，随意取一个在外凸多边形上的点，有多少的概率能取到对应线段与内多边形相交的点。

然后规模是TC的老规矩：50

然后算法就是暴力T_T。但是我暴力好像都写得很长。

第一步：

枚举每条外多边形上的边Point[i]->Point[i+1]，然后再枚举Point[j]和Point[k]，然后搞Point[j]->Point[k]的中垂线(这个有模板T_T)，这个中垂线跑回来和Point[i]->Point[i+1]求交点(没交点就算了)。然后将这些交点按到Point[i]的距离排个序，去重。然后对于这个交点序列，每个点到下一个点形成了线段，然后就找一个到线段离两个端点最远的Point[t]，然后这个线段对应的最远点就是Point[t]了。

第二步：

枚举外多边形上的点Point[i]，然后枚举内多边形上的点，找到一左一右两个交点L和R(可以加多一层循环判是不是所有点都在它左边或者右边)，然后向量Point[i]->L和向量Point[i]->R所夹的位置，就是能够穿过内多边形所对应的位置。然后枚举第一步求的交点序列，如果相邻交点间线段对应的最远点是Point[i]，那么就用Point[i]->L和Point[i]->R这两个直线向它求交点，然后分情况讨论一下(我这里好像显然写长了)。

 

T_T，幸好调对第一个样例以后就Y了，不然得Debug个半死。

【CODE】

const double eps=1e-9;

    int sign(double x){
        if (x<-eps) return -1;
        if (x> eps) return1;
        return0;
    }

    int m,n;
    struct TPoint{
        double x,y;
        TPoint operator + (TPoint oth){
            TPoint ret;
            ret.x=x+oth.x;
            ret.y=y+oth.y;
            return ret;
        }
        TPoint operator – (TPoint oth){
            TPoint ret;
            ret.x=x-oth.x;
            ret.y=y-oth.y;
            return ret;
        }
        TPoint operator * (double oth){
            TPoint ret;
            ret.x=x*oth;
            ret.y=y*oth;
            return ret;
        }
        booloperator != (TPoint oth){
            return (sign(x-oth.x)!=0 || sign(y-oth.y)!=0);
        }
        booloperator == (TPoint oth){
            return sign(x-oth.x)==0 && sign(y-oth.y)==0;
        }
        doubleoperator ^ (TPoint oth){
            return x*oth.y-y*oth.x;
        }
    }Site[55],Dep[55];
   
struct TLine{
    double a,b,c;
};

TPoint Rot90(TPoint A){
    TPoint ret;
    ret.x=-A.y;
    ret.y=A.x;
    return ret;
}
   
TLine Get_Line(TPoint A,TPoint B){
    TLine ret;
    ret.a=A.y-B.y;
    ret.b=B.x-A.x;
    ret.c=B.y*A.x-B.x*A.y;
    return ret;
}

TPoint jiao(TLine A,TLine B){
    TPoint ret;
    ret.x=(A.b*B.c-A.c*B.b)/(A.a*B.b-B.a*A.b);
    ret.y=(A.c*B.a-A.a*B.c)/(A.a*B.b-B.a*A.b);
    return ret;
}

double dis(TPoint A,TPoint B){
    return sqrt((A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y));
}

    pair        pair        ret.second=false;
        TLine L2=Get_Line(A,B);
        if (sign(L.a*L2.b-L2.a*L.b)==0) return ret;
        else{
            ret.first=jiao(L,L2);
            if (sign(min(A.x,B.x)-ret.first.x)<=0 && sign(ret.first.x-max(A.x,B.x))<=0
            &&  sign(min(A.y,B.y)-ret.first.y)<=0 && sign(ret.first.y-max(A.y,B.y))<=0){
                if (ret.first==A || ret.first==B) return ret;
                ret.second=true;
                return ret;
            }
        }
        return ret;
    }
   
    vector     vector     vector     int tttt;
   
    bool cmp(TPoint A,TPoint B){
        return dis(A,Site[tttt])    }
   
    void Div_part(){
        int i,j,k,p;
        for (i=0;i            Cut[i].clear();
            Cut[i].push_back(Site[i]);
            Cut[i].push_back(Site[(i+1)%m]);
            for (j=0;j              for (k=j+1;k                  TPoint mid=(Site[j]+Site[k])*0.5;
                  TPoint dir=Rot90(Site[j]-Site[k]);
                  pair                  if (cross.second) Cut[i].push_back(cross.first);
              }
            tttt=i;
            sort(Cut[i].begin(),Cut[i].end(),cmp);
            TV.clear();
            for (j=0;j              if (j==0 || Cut[i][j]!=Cut[i][j-1]) TV.push_back(Cut[i][j]);
            Cut[i]=TV;
            best[i].clear();
            for (p=0;p                int now=0;
                for (j=1;j                  if ( sign( dis(Site[j],TV[p]) – dis(Site[now],TV[p]) )>=0 && sign( dis(Site[j],TV[p+1]) – dis(Site[now],TV[p+1]) )>=0 )
                    now=j;
                best[i].push_back(now);
            }
        }
    }
   
    double ans;
   
    void Rush(){
        int i,j,k,L,R;
        for (i=0;i            for (j=0;j                bool check=true;
                for (k=0;k                  if ( sign( (Dep[j]-Site[i])^(Dep[k]-Site[i]) ) > 0 )  check=false;
                if (check) { L=j; break; }
            }
            for (j=0;j                bool check=true;
                for (k=0;k                  if ( sign( (Dep[j]-Site[i])^(Dep[k]-Site[i]) ) < 0 ) check=false;
                if (check) {R=j; break;}
            }
            for (j=0;j              for (k=0;k                if (best[j][k]==i){
                    pair                    pair                    TPoint Lp=Cut[j][k];
                    TPoint Rp=Cut[j][k+1];
                    if (crossL.second){
                      if (crossR.second)
                          ans+=dis(crossL.first,crossR.first);
                      else{
                          if (sign( (Dep[L]-Site[i])^(Lp-Site[i]) )<=0 && sign( (Dep[R]-Site[i])^(Lp-Site[i]) )>=0 )
                              ans+=dis(Lp,crossL.first);
                          else
                              ans+=dis(Rp,crossL.first);
                      }
                    }
                    else{
                      if (crossR.second){
                          if (sign( (Dep[L]-Site[i])^(Lp-Site[i]) )<=0 && sign( (Dep[R]-Site[i])^(Lp-Site[i]) )>=0 )
                              ans+=dis(Lp,crossR.first);
                          else
                              ans+=dis(Rp,crossR.first);
                      }
                      else{
                          if (sign( (Dep[L]-Site[i])^(Lp-Site[i]) )<=0 && sign( (Dep[R]-Site[i])^(Lp-Site[i]) )>=0
                          &&  sign( (Dep[L]-Site[i])^(Rp-Site[i]) )<=0 && sign( (Dep[R]-Site[i])^(Rp-Site[i]) )>=0)
                              ans+=dis(Lp,Rp);
                      }
                    }
                }
        }
    }
class Deposit {
public:
    double successProbability(vector         m=siteX.size();
        n=depositX.size();
        for (int i=0;i            Site[i].x=siteX[i];
            Site[i].y=siteY[i];
        }
        for (int i=0;i            Dep[i].x=depositX[i];
            Dep[i].y=depositY[i];
        }
        double Sum=0;
        for (int i=0;i        ans=0;
        Div_part();
        Rush();
        return ans/Sum;
    }
};