作者存档：edward_mj

唉，跌rating了。

250是个很骗人的题目。。。我一开始很迅速地反应到结果只能是2,1,-1。。。然后构造的方法也YY了一下。写完过掉样例以后，突然觉得好像不太靠谱，有点忐忑。然后又跑去换了个dp。最后折腾到只有130+分了。其实很显然本身就是对的啊。。。

500这种求期望的题见到就挂啊。

总是喜欢求和然后除以总方案数这种YY方式。太弱了。我YY的时候甚至觉得每个排列不是等可能的(由于第二个条件)。

然而排列和后面的选取是分步进行的。所以每个排列是等可能的。

于是可以通过枚举边，然后算对应概率，最后加起来的方式求期望值。

各路大神齐集，题目难到奇葩。

ACRush滑铁卢500和1000都挂了……

CLJ神犇爆-25……

还有两target是0的，红色爆0一堆……

‍

然后我一进去我的房间，就看到一个熟悉的ID：felix-halim，然后还有个人拼命YM它、YY着到底是谁，突然想起是建这个网站的人：

http://felix-halim.net/uva/hunting.php?id=29277

UVA帝啊T_T(上面是AekdyCoin的号)

不过后来他爆0了。我们房子唯一一个红的也爆0了……

最后本房一共7个人有分，其中有一个是叉人得的分。

其余都是只pass了250pt……

由于我巨慢的手速和思考速度，T_T，我的250只有122.66分了，最后在DIV1里刚刚好200名。

于是rating就涨回去了，终于从Blue Boy变回Yellow Boy了！！！上次由于插件事件爆0那rating跌得叫一个惨啊……

哎，我太蒟蒻了。

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

然后规模是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;
    }
};