NC13949. River
描述
输入描述
第一行三个整数n,u,t表示河的数量,游泳的速度和时间。 接下来n行,每行两个整数w[i], v[i]表示河的宽度和流速。
输出描述
如果游不过所有的河,输出-1。 否则输出两行。 第一行表示你能游到离出发点多远的地方。 第二行n个数,每个数字通过空格隔开,结尾无空格,表示每条河你游的时间。 要求保留三位小数。
示例1
输入:
2 1 6 1 1 2 1
输出:
11.591 2.000 4.000
C++ 解法, 执行用时: 9ms, 内存消耗: 496K, 提交时间: 2021-05-20 15:07:06
#include<bits/stdc++.h> using namespace std; typedef long double ld; int n,u,t,w[55],v[55]; ld ans[55]; bool judge(ld x){ ld res=0; for(int i=1;i<=n;i++){ ans[i]=sqrt(((x-v[i])*(x-v[i])*w[i]*w[i])/(u*u*((x-v[i])*(x-v[i])-u*u))); res+=ans[i]; } return res<=t; } int main(){ ld x=0,y=0,L=0,R=1e9; scanf("%d%d%d",&n,&u,&t); for(int i=1;i<=n;i++){ scanf("%d%d",&w[i],&v[i]); x+=w[i]; L=max(L,(ld)v[i]+u); } if(u*t<x)puts("-1"); else{ for(int i=1;i<=100;i++){ ld mid=(L+R)*0.5; if(!judge(mid))L=mid; else R=mid; } for(int i=1;i<=n;i++) y+=sqrt(ans[i]*ans[i]*u*u-w[i]*w[i])+v[i]*ans[i]; printf("%.3Lf\n",sqrt(x*x+y*y)); for(int i=1;i<n;i++) printf("%.3Lf ",ans[i]); printf("%.3Lf\n",ans[n]); } return 0; }