分配问题，将小精灵分配给巫妖，巫妖可接收量取决于时间长短，适应性取决于地形

预处理巫妖小精灵对的可行性，就是询问线段 \(AB\) 与圆 \(O\) 是否有交点

过点 \(O\) 作直线 \(AB\) 的垂线，考虑垂足，若垂足不在线段 \(AB\) 上，则问题等价于线段是否存在一段点在圆内

否则通过 \(\overrightarrow{AO} \ast \overrightarrow{AB}\) 计算 \(\overrightarrow{AO}\), \(\overrightarrow{AB}\) 所夹平行四边形面积，进而求得 \(O\) 到直线 \(AB\) 的距离，与半径比较大小即可

列出式子整理一下就可以避免double了！还有不要忘了巫妖有攻击半径

二分时间，用网络流判断可行性，即

由源点向巫妖连施法次数的边，巫妖向小精灵连边，小精灵连向汇点

二分上界为 \(MaxT\ast M\) ，下界为 \(0\) ，最大流等于小精灵数即为可行

#include 
    
     #include 
     
      using std::min;using std::max;const int MAXN=211;const int MAXM=211;const int MAXK=211;const int MAXV=MAXN+MAXM;const int MAXE=MAXN*MAXM+MAXN+MAXM;const int INF=1034567890;int N, M, K;bool Win=true;struct Pos{    int x, y;    Pos(){}    Pos(int _x, int _y){x=_x;y=_y;}    void read(){        scanf("%d%d", &x, &y);    }};Pos operator - (Pos A, Pos B){    return Pos(A.x-B.x, A.y-B.y);}int Len(Pos A){    return A.x*A.x+A.y*A.y;}int Dis(Pos A, Pos B){    return Len(A-B);}int corss(Pos A, Pos B){    return A.x*B.y-A.y*B.x;}int dot(Pos A, Pos B){    return A.x*B.x+A.y*B.y;}struct Elf{    Pos P;    bool OutofTree;    bool Link;} El[MAXM];struct Lich{    Pos P;    int R, T;    bool OutofTree;} L[MAXN];struct Tree{    Pos P;    int R;} T[MAXK];bool Map[MAXN][MAXM];struct Vert{    int FE;    int Bfn, Lev;} V[MAXV];int Vcnt;int Lp[MAXN], Ep[MAXM];int Sour, Sink;struct Edge{    int x, y, f, next, neg;} E[MAXE<<1];int Ecnt;void addE(int a, int b, int c=1){    ++Ecnt;    E[Ecnt].x=a;E[Ecnt].y=b;E[Ecnt].f=c;E[Ecnt].next=V[a].FE;V[a].FE=Ecnt;E[Ecnt].neg=Ecnt+1;    ++Ecnt;    E[Ecnt].y=a;E[Ecnt].x=b;E[Ecnt].f=0;E[Ecnt].next=V[b].FE;V[b].FE=Ecnt;E[Ecnt].neg=Ecnt-1;}int Q[MAXV], Head, Tail;int BFN;bool BFS(int at=Sour){    Head=Tail=1;++BFN;    V[at].Lev=1;    Q[Tail++]=at;    V[at].Bfn=BFN;    while(Head
      
       0;k=E[k].next){            if(E[k].f<=0)   continue;            to=E[k].y;            if(V[to].Bfn==BFN)  continue;            V[to].Lev=V[at].Lev+1;            Q[Tail++]=to;            V[to].Bfn=BFN;        }    }    return V[Sink].Bfn==BFN;}int DFS(int at=Sour, int inc=INF){    if(at==Sink || inc<=0)  return inc;    int ret=0, out;    for(int k=V[at].FE, to;k>0;k=E[k].next){        if(E[k].f<=0)   continue;        to=E[k].y;        if(V[to].Lev!=V[at].Lev+1)  continue;        out=DFS(to, min(E[k].f, inc));        ret+=out;inc-=out;        E[k].f-=out;E[E[k].neg].f+=out;    }    if(inc>0)   V[at].Lev=-1;    return ret;}int DINIC(){    int ret=0;    while(BFS()){        ret+=DFS();    }    return ret;}int Left, Right, Mid;int MaxT;int Cnt(Lich &l, int &t){    if(l.T==0)  return INF;    return t/(l.T)+1;}bool Test(int Time){    for(int i=1;i<=Vcnt;++i)    V[i].FE=0;    Ecnt=0;    for(int i=1;i<=N;++i)   addE(Sour, Lp[i], Cnt(L[i], Time));    for(int i=1;i<=M;++i)   addE(Ep[i], Sink);    for(int i=1;i<=N;++i)        for(int j=1;j<=M;++j)            if(Map[i][j])                addE(Lp[i], Ep[/*i*/j]);    return DINIC()==M;}int main(){        scanf("%d%d%d", &N, &M, &K);    for(int i=1;i<=N;++i){        L[i].P.read();        scanf("%d%d", &L[i].R, &L[i].T);    }    for(int i=1;i<=M;++i)        El[i].P.read();    for(int i=1;i<=K;++i){        T[i].P.read();        scanf("%d", &T[i].R);    }        for(int i=1;i<=N;++i){        L[i].OutofTree=true;        for(int j=1;j<=K;++j)            if(Dis(L[i].P, T[j].P)<=T[j].R*T[j].R)                L[i].OutofTree=false;    }        for(int i=1;i<=M;++i){        El[i].OutofTree=true;        for(int j=1;j<=K;++j){            if(Dis(El[i].P, T[j].P)<=T[j].R*T[j].R)                El[i].OutofTree=false;        }    }        for(int i=1;i<=M;++i)        if(!El[i].OutofTree){            Win=false;            break;        }        if(!Win){        puts("-1");        return 0;    }        for(int i=1;i<=N;++i){        if(!L[i].OutofTree) continue;        for(int j=1, c;j<=M;++j){            if(!El[j].OutofTree)    continue;            if(Dis(El[j].P, L[i].P)>L[i].R*L[i].R)  continue;            c=1;            for(int k=1, Dot, Corss;k<=K && c>0;++k){                Dot=dot(El[j].P-L[i].P, T[k].P-L[i].P);                if(Dot>0 && Dot
       
        0){                //addE(Lp[i], Ep[j]);                //printf("%d %d\n", i, j);                Map[i][j]=true;                El[j].Link=true;            }        }    }        for(int i=1;i<=M;++i)        if(!El[i].Link){            Win=false;            break;        }        if(!Win){        puts("-1");        return 0;    }        for(int i=1;i<=N;++i)   Lp[i]=++Vcnt;    for(int i=1;i<=M;++i)   Ep[i]=++Vcnt;    Sour=++Vcnt;Sink=++Vcnt;        for(int i=1;i<=N;++i)   MaxT=max(MaxT, L[i].T);        Left=0;Right=MaxT*M;    while(Left
        
         >1;        if(Test(Mid))   Right=Mid;        else    Left=Mid+1;    }    Mid=(Left+Right)>>1;        printf("%d\n", Mid);        return 0;}/*2 3 1-100 0 100 3100 0 100 5-100 -10100 10110 115 5 105*/