思路比较显然:二分答案,流流流

但是实现的时候感觉自己数学捉急。。

一开始算了个直线到点距离。。。。

应该是线段到点距离

 #include <bits/stdc++.h>
#define sqr(x) ((x)*(x))
#define MAXN 50000
#define TO (n+m+2)
#define FROM (n+m+1)
#define PO (n+m+2)
#define INF 2000000000
#define mid (l+r>>1)
using namespace std;
int n,m,k,LI=,ans;
int to[MAXN],w[MAXN],nex[MAXN],fir[MAXN];
int h[MAXN],qq[MAXN],flo[MAXN],id[MAXN];
int ti[MAXN],x[MAXN],y[MAXN],X[MAXN],Y[MAXN],r[MAXN],p[MAXN],q[MAXN],R[MAXN];
void add(int p,int q,int o)
{
to[LI]=q;w[LI]=o;nex[LI]=fir[p];fir[p]=LI;LI++;
to[LI]=p;w[LI]=;nex[LI]=fir[q];fir[q]=LI;LI++;
}
bool bfs()//计算层次图
{
int head=-,tail=;
for(int i=;i<=PO;i++) h[i]=-;
qq[]=FROM;h[FROM]=;// h[i]:点i的层数
while(head!=tail)
{
int x=qq[++head];
for(int i=fir[x];i;i=nex[i])
if(flo[i]&&h[to[i]]==-)
{
h[to[i]]=h[x]+;
qq[++tail]=to[i];
}
}
return h[TO]!=-;
}
int dfs(int x,int f)//增广路:到点x最大容量为 f
{
if(x==TO)return f;
int w,used=;
for(int i=fir[x];i;i=nex[i])
if(h[to[i]]==h[x]+)
{
w=dfs(to[i],min(flo[i],f-used));
flo[i]-=w; flo[i^]+=w;
used+=w;if(used==f)return f;
}
if(!used)h[x]=-;
return used;
}
int dinic() //%usqwedf
{
int ans=;
while(bfs())
ans+=dfs(FROM,1e9);
return ans;
}
bool ok(int time)
{
for(int i=;i<=n;i++)
w[id[i]]=time/ti[i]+;
for(int i=;i<LI;i++)
flo[i]=w[i];
return(dinic()==m);
}
int main()
{
// freopen("1.in","r",stdin);
scanf("%d%d%d",&n,&m,&k);
for(int i=;i<=n;i++)
scanf("%d%d%d%d",&x[i],&y[i],&r[i],&ti[i]);
for(int i=;i<=m;i++)
scanf("%d%d",&X[i],&Y[i]);
for(int i=;i<=k;i++)
scanf("%d%d%d",&p[i],&q[i],&R[i]);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
bool flag=sqr(x[i]-X[j])+sqr(y[i]-Y[j])<=sqr(r[i]);
if(!flag) continue;
long long a=y[i]-Y[j],b=X[j]-x[i],c=x[i]*Y[j]-y[i]*X[j];
for(int o=;o<=k;o++)
if(sqr(a*p[o]+b*q[o]+c)<=sqr(R[o])*(sqr(a)+sqr(b)) && (sqr(x[i]-p[o])+sqr(y[i]-q[o])<=sqr(R[o]) || sqr(X[j]-p[o])+sqr(Y[j]-q[o])<=sqr(R[o])))
{
flag=;
break;
}
if(flag)
add(i,j+n,);
}
for(int i=;i<=m;i++)
add(i+n,TO,);
for(int i=;i<=n;i++)
id[i]=LI,add(FROM,i,);
int l,r;
for(l=,r=;l<r;)
if(ok(mid)) r=mid;else l=mid+;
if(ok(l))
printf("%d\n",l);
else
puts("-1");
return ;
}

最新文章

  1. Base64原理解析
  2. MySQL命令大全:MySQL常用命令手册、MySQL命令行大全、查询工具
  3. C#:使用Twain协议实现扫描仪连续扫描
  4. iPhone不为人知的功能常用技巧,看完后才发现很多用iPhone的人实在是愧对乔布斯! - imsoft.cnblogs
  5. webServer xampp的安装及使用
  6. jQuery提交Json数据到Webservice,并接收返回的Json数据
  7. DNN学习
  8. codeforces 387C George and Number
  9. 字符串匹配算法-BM
  10. text选中后displa出label内容
  11. jasmine官方api参考
  12. 深入浅出AQS之共享锁模式
  13. C++多线程学习之(一)——并发与多线程
  14. ng-book札记——依赖注入
  15. Java并发框架——AQS之阻塞与唤醒
  16. vue的动态路由(登录之后拿到动态路由通过addRouters()动态添加路由)
  17. 我眼里K-Means算法
  18. mysql根据分组和条件查询以后如何统计记录的条数
  19. Python基础理论 - 函数
  20. UVA1434-The Rotation Game(迭代加深搜索)

热门文章

  1. Intellij IDEA 14代码错误提示如何调出来
  2. Java_正则_00_资源贴
  3. Linux_服务器_02_在linux上怎么看eclipse控制台输出语句
  4. ubuntu的root权限设置
  5. 【boost】ptree 读写中文的问题
  6. PageMethods
  7. [转] 编写高效的 CSS 选择器
  8. linux 中C语言便于调试的宏定义编写及 __FILE__,__FUNCTION__, __LINE__参数使用
  9. python3中,pycharm中怎么连接数据库
  10. &lt;正则吃饺子&gt; :关于微信支付的简单总结说明(一)