Description
WJJ喜欢“魔兽争霸”这个游戏。在游戏中，巫妖是一种强大的英雄，它的技能Frozen Nova每次可以杀死一个小精灵。我们认为，巫妖和小精灵都可以看成是平面上的点。 当巫妖和小精灵之间的直线距离不超过R，且巫妖看到小精灵的视线没有被树木阻挡（也就是说，巫妖和小精灵的连线与任何树木都没有公共点）的话，巫妖就可以瞬间杀灭一个小精灵。 在森林里有N个巫妖，每个巫妖释放Frozen Nova之后，都需要等待一段时间，才能再次施放。不同的巫妖有不同的等待时间和施法范围，但相同的是，每次施放都可以杀死一个小精灵。 现在巫妖的头目想知道，若从0时刻开始计算，至少需要花费多少时间，可以杀死所有的小精灵？
Input
输入文件第一行包含三个整数N、M、K(N,M,K<=200)，分别代表巫妖的数量、小精灵的数量和树木的数量。 接下来N行，每行包含四个整数x, y, r, t，分别代表了每个巫妖的坐标、攻击范围和施法间隔（单位为秒）。 再接下来M行，每行两个整数x, y，分别代表了每个小精灵的坐标。 再接下来K行，每行三个整数x, y, r，分别代表了每个树木的坐标。 输入数据中所有坐标范围绝对值不超过10000，半径和施法间隔不超过20000。
Output
输出一行，为消灭所有小精灵的最短时间（以秒计算）。如果永远无法消灭所有的小精灵，则输出-1。
Sample Input
2 3 1
-100 0 100 3
100 0 100 5
-100 -10
100 10
110 11
5 5 10
Sample Output
5

题解

这题大概二分下答案然后建图跑网络流
但是难点不是这个，而是判断有没有被树挡住
可能只是对于我而言
由于基本没什么高中数学知识。。于是只能瞎搞

以下ORZTYB

我们知道，其实这道题就是判断一条线段是否与园有交点
如果点到直线的距离都没有的话，那么就肯定没有了
有以下两种情况：
1.点作垂线与直线的交点在线段上
2…….不在线段上

对于第一种情况，我们可以直接用该垂线的长度来当做最短距离判断就可以了
然而对于第二种情况，我们就选取圆心到两个端点较短的一个距离作为最短距离判断

但是我们怎么判断这个交点在哪里呢？

我们来画一张图

A，B是要求的线段，O是圆心，C是垂足
我们记OA，OB长的一段叫做H
我们可以发现，如果在线段上，那么，以OC作直角边，H作斜边，另外一条直角边的长度是小于AB的
反之长度则是大于AB的

于是这样就大功告成了。。
至于怎么求出OC，不会的可以自行上网查一下点到直线的距离，我这里就懒得写了

CODE：

#include<cstdio>
#include<cstdlib>
#include<queue>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
const int N=205*2;
const int MAX=1<<29;
int n,m,k;
struct qq{int x,y,r,t;}a[N],b[N],c[N];
bool ooo[N][N];//第i个巫妖能不能看到第j个小精灵
double dis (qq a,qq b)//距离的平方 
{return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
void prepare ()
{for (int u=1;u<=n;u++){for (int i=1;i<=m;i++)//这个巫妖能不能看到这个小精灵 {if ((int)dis(a[u],b[i])>a[u].r*a[u].r) {ooo[u][i]=false;continue;}bool tf=true;int x1=a[u].x,y1=a[u].y;int x2=b[i].x,y2=b[i].y;int A=(y2-y1),B=(x1-x2),C=-(A*x1+B*y1);//A*x1+B*y1+C=0//A*x2+B*y2+C=0//A*x1+B*y1=A*x2+B*y2//A*(x1-x2)=B*(y2-y1)for (int j=1;j<=k;j++)//这个树木会不会挡住 {double Dis;double d=(abs((double)(A*c[j].x+B*c[j].y+C)/(double)sqrt(A*A+B*B)));//得到圆心到这个节点的距离double shen=max(dis(c[j],a[u]),dis(c[j],b[i]));//  printf("NO:%d %d %lf %lf %lf\n",u,i,d,shen,dis(a[u],b[i]));if (shen-d*d<dis(a[u],b[i])) //在线段上 Dis=d*d;else Dis=min(dis(a[u],c[j]),dis(b[i],c[j]));if (Dis<c[j].r*c[j].r){tf=false;break;}}//printf("YES:%d %d %d\n",u,i,tf);ooo[u][i]=tf; }}/*for (int u=1;u<=n;u++){for (int i=1;i<=m;i++)printf("YES:%d ",ooo[u][i]);printf("\n");}*/
}
struct qy{
   int x,y,z,last;}s[N*N*2];
int num,last[N];
int st,ed;
void init (int x,int y,int z)
{num++;s[num].x=x;s[num].y=y;s[num].z=z;s[num].last=last[x];last[x]=num;swap(x,y);z=0;num++;s[num].x=x;s[num].y=y;s[num].z=z;s[num].last=last[x];last[x]=num;
}
int h[N];
bool Bt ()
{memset(h,-1,sizeof(h));h[st]=1;queue<int> q;q.push(st);while (!q.empty()){int x=q.front();q.pop();for (int u=last[x];u!=-1;u=s[u].last){int y=s[u].y;if (s[u].z>0&&h[y]==-1){h[y]=h[x]+1;q.push(y);}}}return h[ed]!=-1;
}
int mymin (int x,int y){
   return x<y?x:y;}
int dfs (int x,int f)
{if (x==ed) return f;int s1=0;for (int u=last[x];u!=-1;u=s[u].last){int y=s[u].y;if (s[u].z>0&&h[y]==h[x]+1&&s1<f){int lalal=dfs(y,mymin(s[u].z,f-s1));s1+=lalal;s[u].z-=lalal;s[u^1].z+=lalal;}}if (s1==0) h[x]=-1;return s1;
}
bool check (int x)//我有这么多时间行不行 
{num=1;memset(last,-1,sizeof(last));for (int u=1;u<=n;u++) init(st,u,x/a[u].t+1);for (int u=1;u<=m;u++) init(u+n,ed,1);for (int u=1;u<=n;u++)for (int i=1;i<=m;i++)if (ooo[u][i])init(u,i+n,1);int ans=0;while (Bt()) ans=ans+dfs(st,MAX);return ans==m;
}
void solve ()
{for (int u=1;u<=m;u++){bool tf=false;for (int i=1;i<=n;i++)if (ooo[i][u]) tf=true;if (tf==false) {
   printf("-1\n");return ;}}int l=0,r=MAX;int ans;while (l<=r){int mid=(l+r)>>1;if (check(mid)) {ans=mid;r=mid-1;}else l=mid+1;}printf("%d",ans);
}
void Ins ()
{scanf("%d%d%d",&n,&m,&k);st=n+m+1;ed=st+1;for (int u=1;u<=n;u++) scanf("%d%d%d%d",&a[u].x,&a[u].y,&a[u].r,&a[u].t);//巫妖 for (int u=1;u<=m;u++) scanf("%d%d",&b[u].x,&b[u].y);//小精灵 for (int u=1;u<=k;u++) scanf("%d%d%d",&c[u].x,&c[u].y,&c[u].r);//树木
}
int main()
{Ins();prepare();solve();return 0;
}