Way Selection

背景

小杉家族遭遇了前所未有的大危机
他想知道怎么逃生

描述

小杉家族r个人正在一片空地上散步,突然,外星人来了……
留给小杉家族脱逃的时间只有t秒,每个小杉都有一个跑的速度v
总共有a个传送点,小杉们必须在t秒内到达传送点才能脱逃
另外一个小杉进入一个传送点以后,该传送点就会消失
现在请你安排一种方案,使脱逃的小杉尽可能的多

格式

输入格式

每组测试数据的
第一行有三个整数r和a和t(0<a,r,t<=1000)
第二行有a对实数,第i对数表示第i个传送点的坐标,这些坐标绝对值均不超过1e6
接下来r行,每行有三个实数x,y,v,表示第i个小杉的坐标和奔跑的速度

输出格式

对每组测试数据输出一行
仅有一个整数s
表示最多有多少个小杉能成功脱逃

样例1

样例输入1

1 1 1
1 1
1 1 1

样例输出1

1

限制

每个测试点1s

提示

简单的很,别想复杂了

来源

lolanv

 #include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
inline void read(int &x){x = ;char ch = getchar();char c = ch;while(ch > '' || ch < '')c = ch, ch = getchar();while(ch <= '' && ch >= '')x = x * + ch - '', ch = getchar();if(c == '-')x = -x;}
const int MAXN = + ; int g[MAXN][MAXN],by[MAXN],lk[MAXN];
int r,a,t,ans;
double x[MAXN],y[MAXN],v[MAXN],xx[MAXN],yy[MAXN]; int find(int v)
{
for(int i = ;i <= a;i ++)
{
if(!by[i] && g[v][i])
{
by[i] = ;
if((!lk[i]) || find(lk[i]))
{
lk[i] = v;
return ;
}
}
}
return ;
} int main()
{
read(r);read(a);read(t);
for(int i = ;i <= a;i ++)
scanf("%lf %lf", &x[i], &y[i]);
for(int i = ;i <= r;i ++)
scanf("%lf %lf %lf", &xx[i], &yy[i], &v[i]);
for(int i = ;i <= a;i ++)
{
for(int j = ;j <= r;j ++)
{
g[j][i] = (sqrt((x[i] - xx[j]) * (x[i] - xx[j]) + (y[i] - yy[j]) * (y[i] - yy[j])) <= v[j] * t);
}
}
for(int i = ;i <= r;i ++)
{
memset(by, , sizeof(by));
if(find(i))ans ++;
}
printf("%d", ans);
return ;
}

最新文章

  1. git使用简单教程
  2. Atitit selenium3 新特性
  3. java入门基础知识点总结
  4. 【转】一个非常常见但容易被忽略的c++问题——用IPML模式可以解决
  5. python调用windows api
  6. [原创]Scala学习:for,function,lazy
  7. Content Providers详解
  8. web前端技术归类
  9. 面试题 ARC
  10. [认证授权] 4.OIDC(OpenId Connect)身份认证授权(核心部分)
  11. selenium webdriver使用click一直失效问题的几种解决方法
  12. TZOJ 5694 区间和II(树状数组区间加区间和)
  13. ES6和ES5变量声明的区别(var let const)
  14. TCP/IP学习20180630-数据链路层-router choose
  15. Python中字典和集合的用法
  16. Confluence 6 配置边栏
  17. SVG 学习&lt;五&gt; SVG动画
  18. CSS只是进化的一部分
  19. [转]webMethods公司简介
  20. Activity的setResult方法

热门文章

  1. centos 6.5 安装dotnet core 2.2
  2. day 48 jQuery快速入门
  3. HBase 表和Region
  4. Leetcode139. Word Break单词拆分
  5. 验证sll证书与密钥
  6. lc6 ZigZag Conversion
  7. 快速傅里叶变换(FFT)学习
  8. CF集萃3
  9. Laravel 错误处理
  10. java 用户注册登陆Demo