标题效果

有着n巫妖。m精灵。k木。他们都有自己的位置坐标表示。冷却时间，树有覆盖范围。

假设某个巫妖攻击精灵的路线（他俩之间的连线）经过树的覆盖范围，表示精灵被树挡住巫妖攻击不到。求巫妖杀死所有精灵的时间。若无法所有杀死输出-1；

解题思路：

推断巫妖能否打到精灵用线段与点的最短距离来推断，若最短距离小于树的覆盖范围，就攻击不到。

最小时间能够跑费用流来解决，也能够二分图的最优匹配。

以下是代码：

#include <set>

#include <map>

#include <queue>

#include <math.h>

#include <vector>

#include <string>

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <iostream>

#include <cctype>

#include <algorithm>

#define eps 1e-6

#define pi acos(-1.0)

#define inf 107374182

#define inf64 1152921504606846976

#define lc l,m,tr<<1

#define rc m + 1,r,tr<<1|1

#define zero(a) fabs(a)<eps

#define iabs(x)  ((x) > 0 ? (x) : -(x))

#define clear1(A, X, SIZE) memset(A, X, sizeof(A[0]) * (min(SIZE,sizeof(A))))

#define clearall(A, X) memset(A, X, sizeof(A))

#define memcopy1(A , X, SIZE) memcpy(A , X ,sizeof(X[0])*(SIZE))

#define memcopyall(A, X) memcpy(A , X ,sizeof(X))

#define max( x, y )  ( ((x) > (y)) ?

(x) : (y) )

#define min( x, y )  ( ((x) < (y)) ? (x) : (y) )

using namespace std;

struct Point

{

    double x,y;

} hitted[205];

struct node1

{

    double r;

    int t;

    Point p;

} att[205];

struct node3

{

    double r;

    Point p;

} tree[205];

int n,m,K;

double Distance(Point a, Point b)

{

    return sqrt((a.x-b.x)*(a.x-b.x)*1.0 + 1.0*(a.y-b.y)*(a.y-b.y));

}

double xmult(Point p1, Point p2, Point p)

{

    return (p1.x-p.x)*(p2.y-p.y) - (p2.x-p.x)*(p1.y-p.y);

}

double disptoseg(Point p, Point a ,Point b)

{

    Point t = p;

    t.x += a.y-b.y, t.y += b.x-a.x;

    if(xmult(a,t,p)*xmult(b,t,p)>eps)

        return Distance(p,a) < Distance(p,b)? Distance(p,a) : Distance(p,b);

    return fabs(xmult(p, a, b))/Distance(a, b);

}

int head[450],cnt;

struct node

{

    int u,v,w,f,next;

} edge[230*230*20];

void addedge(int u,int v,int w,int f)

{

    edge[cnt].u=u;

    edge[cnt].v=v;

    edge[cnt].w=w;

    edge[cnt].f=f;

    edge[cnt].next=head[u];

    head[u]=cnt++;

    edge[cnt].u=v;

    edge[cnt].v=u;

    edge[cnt].w=-w;

    edge[cnt].f=0;

    edge[cnt].next=head[v];

    head[v]=cnt++;

}

int pre[450];

bool vis[450];

bool spfa()

{

    int i;

    //clearall(pre,-1);

    pre[n+m+1]=-1;

    pre[n+m]=-1;

    int dis[450];

    clearall(dis,0x3f3f);

    queue <int >q;

    dis[n+m]=0;

    vis[n+m]=true;

    q.push(n+m);

    while(!q.empty())

    {

        int t=q.front();

        q.pop();

        i=head[t];

        vis[t]=false;

        while(i!=-1)

        {

            if(edge[i].f>0&&dis[edge[i].v]>dis[t]+edge[i].w)

            {

                dis[edge[i].v]=dis[t]+edge[i].w;

                pre[edge[i].v]=i;

                if(!vis[edge[i].v])

                {

                    vis[edge[i].v]=true;

                    q.push(edge[i].v);

                }

            }

            i=edge[i].next;

        }

    }

    if(pre[n+m+1]==-1)return false;

    return true;

}

bool cnthit[205];

double input()

{

    char s=getchar();

    double ans=0;

    while((s<'0'||s>'9')&&s!='-')

    {

        s=getchar();

    }

    bool flat=false;

    if(s=='-')

    {

        flat=true;

        s=getchar();

    }

    while(s>='0'&&s<='9')

    {

        ans*=10;

        ans+=s-'0';

        s=getchar();

    }

    if(flat)ans=-ans;

    return ans;

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d%d%d",&n,&m,&K);

        for(int i=0; i<n; i++)

        {

            att[i].p.x=input();

            att[i].p.y=input();

            att[i].r=input();

            att[i].t=input();

        }

        for(int i=0; i<m; i++)

        {

            hitted[i].x=input();

            hitted[i].y=input();

        }

        for(int i=0; i<K; i++)

        {

            tree[i].p.x=input();

            tree[i].p.y=input();

            tree[i].r=input();

        }

        clearall(head,-1);

        clearall(cnthit,0);

        cnt=0;

        for(int i=0; i<n; i++)

        {

            int cnt1=0;

            for(int j=0; j<m; j++)

            {

                bool flat=true;

                if(Distance(att[i].p, hitted[j]) <= att[i].r)

                {

                    for(int k=0; k<K; k++)

                    {

                        if(disptoseg(tree[k].p,att[i].p,hitted[j])<=tree[k].r)

                        {

                            flat=false;

                            break;

                        }

                    }

                    if(flat)

                    {

                        cnthit[j]=true;

                        addedge(i,n+j,0,1);

                        addedge(n+m,i,att[i].t*cnt1,1);

                        cnt1++;

                    }

                }

            }

        }

        for(K=0; K<m; K++)

        {

            if(cnthit[K]==false)

            {

                break;

            }

        }

        if(K!=m)

        {

            puts("-1");

            continue;

        }

        for(int i=0; i<m; i++)

        {

            addedge(i+n,n+m+1,0,1);

        }

        int ans=0;

        while(spfa())

        {

            int max1=inf;

            int p=pre[n+m+1];

            while(p!=-1)

            {

                max1=min(max1,edge[p].f);

                p=pre[edge[p].u];

            }

            p=pre[n+m+1];

            while(p!=-1)

            {

                edge[p].f-=max1;

                edge[p^1].f+=max1;

                p=pre[edge[p].u];

            }

        }

        for(int i=head[n+m];i!=-1;i=edge[i].next)

        {

            if(edge[i].f==0)ans=max(ans,edge[i].w);

        }

        printf("%d\n",ans);

    }

    return 0;

}