「vijos1212」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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
#include<iostream> #include<cstring> #include<cmath> using namespace std; int r,a,t; double px[1001],py[1001]; int lk[1001],y[1001],mp[1001][1001]; int ans=0; bool pd(double x,double y,double v,int k) { if(v*t>=sqrt((x-px[k])*(x-px[k])+(y-py[k])*(y-py[k])))return 1; return 0; } bool find(int v) { for(int i=1;i<=a;i++) if(mp[v][i]&&!y[i]) { y[i]=1; if(!lk[i]||find(lk[i])) { lk[i]=v; return 1; } } return 0; } int main() { double xx,yy,v; cin>>r>>a>>t; for(int i=1;i<=a;i++) cin>>px[i]>>py[i]; for(int i=1;i<=r;i++) { cin>>xx>>yy>>v; for(int j=1;j<=a;j++) { if(pd(xx,yy,v,j))mp[i][j]=1; } } for(int i=1;i<=r;i++) { memset(y,0,sizeof(y)); if(find(i))ans++; } cout<<ans; return 0; } |
Subscribe
计数器 9787371
OI 课件=>
OI 课件=>