首先很好想到我们应该预处理出来每一个巫妖王能攻击到的精灵。
那么这就是一个几何题。
对于每一组精灵与巫妖王，设巫妖王坐标为 \((x_1,y_1)\)，精灵坐标为 \((x_2,y_2)\)。不考虑树的影响，若巫妖王要看到精灵，那么得满足：
\((x_1-x_2)^2+(y_1-y_2)^2\le r^2\)
用勾股定理或是两点间距离公式可以推出。
那么现在有了树的影响，对于每一棵树，我们都得计算它是否会遮挡视野。
如果一棵树会遮挡视野，当且仅当树经过了精灵与巫妖王的连线。
可以利用解析式求解。
精灵与巫妖王的连线斜率为：\(k_1=\frac{y_1-y_2}{x_1-x_2}\)。
代入直线解析式 \(y=k_1x+b_1\) 得截距。
\[\begin{aligned} &y=\frac{y_1-y_2}{x_1-x_2}x+b_1\\ &b_1=y-\frac{y_1-y_2}{x_1-x_2}x \end{aligned}\]得到解析式后要求树是否会挡路，那么就要求树到这儿的最短距离，即垂线段长度，这里依然用的解析法。
垂线段斜率：\(k_2=-\frac{1}{k_1}\)
垂线段截距：
\[\begin{aligned} &y=k_2x+b_2\\ &b_2=y-k_2x\\ &b_2=y+\frac{x}{k_1}\\ &b_2=y+\frac{x}{\frac{y_1-y_2}{x_1-x_2}}\\ &b_2=y+\frac{x\times(x_1-x_2)}{y_1-y_2} \end{aligned}\]最后解交点坐标 \((x_3,y_3)\)：
\[\begin{aligned} &k_1x_3+b_1=k_2x_3+b_2\\ &(k_1-k_2)x_3=b_2-b_1\\ &x_3=\frac{b_2-b_1}{k_1-k_2}\\ &y_3=k_1x_3+b_1\\ &y_3=k_1\times \frac{b_2-b_1}{k_1-k_2}+b_1 \end{aligned}\]如果树会挡路当且仅当交点在线段上，且交点距离树的距离小于半径 \(r_2\)。
若交点在线段上，那么 \(x_3\ge\min(x_1,x_2)\) 且 \(x_3\le\max(x_1,x_2)\)
若距离小于半径，设树的坐标为 \((x_4,y_4)\)。
那么 \(\sqrt{(x_4-x_3)^2+(y_4-y_3)^2}<r_2\)
由于此时坐标为浮点数，可以利用开方解决。
预处理做完后，就开始求时间花费了。
如果抛开冷却不谈，而是求本题有无解，仅仅是问对于每一个精灵是否能有一个巫妖王与之匹配。
如果再限制每个巫妖王施法次数，就是一个最大流问题。
连接源点与每一个巫妖王，边权是该巫妖王可攻击次数。再连接每一个巫妖王与可以攻击到的精灵，边权赋为 \(1\)，因为一个巫妖王只能攻击一次相同的精灵。最后连接每个精灵与汇点，边权为 \(1\)，因为每个精灵只能死一次。最后跑最大流即可得出是否有解。
现在有了冷却时间，实际上在一定时间 \(time\) 内第 \(i\) 个巫妖王可攻击次数为 \(time\div t_i+1\)。
而本题答案满足单调性，所以可以二分时答案，找到每个巫妖王的攻击次数，每一次跑一个最大流，就可以得到答案了。
约等于二分图匹配所以复杂度为 \(O((n+m)\times\sqrt {n+m})\)。
预处理复杂度为 \(O(nmk)\)。
#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
#include<queue>
#include<cstring>
using namespace std;
const int N=505;
int n,m,k,num[N],dep[N],vis[N];
struct node
{
int to,data;
};
vector<node>t[N];
vector<int>p[N];
struct wyw
{
int x,y,r,t;
}a[N];
struct xjl
{
int x,y;
}b[N];
struct tree
{
int x,y,r;
}c[N];
inline int tabs(int x)
{
return x>0?x:-x;
}
bool bfs()
{
memset(dep,0,sizeof(dep));
queue<int>q;
q.push(0);
dep[0]=1;
while(!q.empty())
{
int x=q.front();
q.pop();
int len=t[x].size();
for(int i=0;i<len;i++)
{
if(t[x][i].data&&!dep[t[x][i].to])dep[t[x][i].to]=dep[x]+1,q.push(t[x][i].to);
}
}
if(dep[n+m+1])return true;
return false;
}
int dfs(int x,int num)
{
if(x==n+m+1)return num;
if(vis[x])return 0;
vis[x]=1;
int len=t[x].size();
for(int i=0;i<len;i++)
{
if(t[x][i].data&&dep[t[x][i].to]==dep[x]+1)
{
int res=dfs(t[x][i].to,min(num,t[x][i].data));
if(res)
{
t[x][i].data-=res;
t[t[x][i].to][p[x][i]].data+=res;
return res;
}
}
}
return 0;
}
int main()
{
//freopen("cold.in","r",stdin);
//freopen("cold.out","w",stdout);
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++)scanf("%d%d%d%d",&a[i].x,&a[i].y,&a[i].r,&a[i].t),num[i]=-a[i].t;
for(int i=1;i<=m;i++)scanf("%d%d",&b[i].x,&b[i].y);
for(int i=1;i<=k;i++)scanf("%d%d%d",&c[i].x,&c[i].y,&c[i].r);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if((a[i].x-b[j].x)*(a[i].x-b[j].x)+(a[i].y-b[j].y)*(a[i].y-b[j].y)>a[i].r*a[i].r)continue;
bool flag=1;
for(int q=1;q<=k;q++)
{
double xielv=1.0*(a[i].y-b[j].y)/(1.0*(a[i].x-b[j].x));
if(a[i].x==b[j].x)xielv=1e-15;
double jieju=a[i].y-1.0*a[i].x*xielv;
double xl=-1.0/xielv;
double jj=c[q].y-1.0*c[q].x*xl;
double xx=(jj-jieju)/(xielv-xl);
double yy=xx*xielv+jieju;
if(xx+1e-5>min(a[i].x,b[j].x)&&xx-1e-5<max(a[i].x,b[j].x)&&sqrt((xx-c[q].x)*(xx-c[q].x)+(yy-c[q].y)*(yy-c[q].y))-1e-5<c[q].r)flag=0;
}
if(flag)
{
t[i].push_back((node){j+n,1}),t[j+n].push_back((node){i,0});
p[i].push_back(t[j+n].size()-1),p[j+n].push_back(t[i].size()-1);
}
}
t[i].push_back((node){0,0});
p[0].push_back(t[i].size()-1);
}
for(int i=1;i<=m;i++)
{
t[i+n].push_back((node){1+n+m,1}),t[1+n+m].push_back((node){i,0});
p[n+m+1].push_back(t[i+n].size()-1),p[i+n].push_back(t[n+m+1].size()-1);
}
for(int i=1;i<=n;i++)p[i].push_back(0);
int l=0,r=1e9;
while(l<r)
{
int mid=(l+r)>>1;
t[0].clear();
for(int i=1;i<=n;i++)
{
t[0].push_back((node){i,mid/a[i].t+1});
p[i][p[i].size()-1]=t[0].size()-1;
}
for(int i=1;i<=n+m;i++)
{
int len=t[i].size();
for(int j=0;j<len;j++)
{
if(i<t[i][j].to)t[i][j].data=1;
else t[i][j].data=0;
}
}
int ans=0;
while(bfs())
{
memset(vis,0,sizeof(vis));
int sum=dfs(0,1e9);
while(sum)
{
ans+=sum;
memset(vis,0,sizeof(vis));
sum=dfs(0,1e9);
}
}
if(ans==m)r=mid;
else l=mid+1;
}
int mid=l;
t[0].clear();
for(int i=1;i<=n;i++)
{
t[0].push_back((node){i,mid/a[i].t+1});
p[i][p[i].size()-1]=t[0].size()-1;
}
for(int i=1;i<=n+m;i++)
{
int len=t[i].size();
for(int j=0;j<len;j++)
{
if(i<t[i][j].to)t[i][j].data=1;
else t[i][j].data=0;
}
}
int ans=0;
while(bfs())
{
memset(vis,0,sizeof(vis));
int sum=dfs(0,1e9);
while(sum)
{
ans+=sum;
memset(vis,0,sizeof(vis));
sum=dfs(0,1e9);
}
}
if(ans!=m)printf("-1");
else printf("%d",l);
return 0;
}