## 【BZOJ 4570】[SCOI2016] 妖怪

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 1000000+9;
const double INF = 1e100;

struct Point{
#define Vector Point
int x,y;
inline Point() {}
inline Point(int _x, int _y):x(_x),y(_y){}
inline bool operator < (const Point &B) const{return (x<B.x)||(x==B.x&&y<B.y);}
inline Point operator - (const Point &B) {Point C; C.x=x-B.x; C.y=y-B.y; return C;}
inline LL operator * (const Point &B) {return (LL)x*B.y - (LL)y*B.x;}
}p[N],con[N];
int n,cnt;
double vout = INF;

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

inline void ConvexHull(){
con[++cnt] = p[n];
for (int i=n-1;i;i--) {
while (cnt > 1 && (con[cnt]-con[cnt-1])*(p[i]-con[cnt-1]) <= 0LL) cnt--;
con[++cnt] = p[i];
}
while (cnt > 1 && con[cnt].y <= con[cnt-1].y) cnt--;
}

int main(){
sort(p+1,p+1+n); ConvexHull(); double R, L=INF, MN;
for (int i=1;i<=cnt;i++) {
Vector v = con[i+1] - con[i];
swap(L, R); L = i!=cnt?(double)-v.y / v.x:0;
MN = sqrt((double)con[i].y / con[i].x);
if (R < MN) vout = min(vout, con[i].x*R + con[i].y/R + con[i].x + con[i].y);
else if (L > MN) vout = min(vout, con[i].x*L + con[i].y/L + con[i].x + con[i].y);
else vout = min(vout, con[i].x*MN + con[i].y/MN + con[i].x + con[i].y);
} printf("%.4lf\n",vout);
return 0;
}


## 【NOI六连测】[D1T2] 过河

$$\begin{array}{l} \partial (({V_i} + \sqrt {{u^2} – \frac{{W_i^2}}{{{t^2}}})} \cdot t) = \partial ({V_i} \cdot t) + \partial (\sqrt {{u^2} \cdot {t^2} – W_i^2} )\\ = {V_i} + \partial ({u^2} \cdot {t^2}) \cdot \frac{{0.5}}{{\sqrt {{u^2} \cdot {t^2} – W_i^2} }} = {V_i} + \frac{{{u^2} \cdot t}}{{\sqrt {{u^2} \cdot {t^2} – W_i^2} }} \end{array}$$

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#define LD long double
using namespace std;

const int MAXN = 50+9;
const LD EPS = 1e-15;

int n;
LD v[MAXN],w[MAXN],ans[MAXN];
LD disx,MXv,u,t;

inline LD cal(LD k){
LD ret = 0;
for (int i=1;i<=n;i++){
LD r = (k-v[i])*(k-v[i]);
LD t = sqrt(r*w[i]*w[i]/(r*u*u-u*u*u*u));
ans[i] = t; ret += t;
}
return ret;
}

inline double GetAns(){
LD ret = 0;
for (int i=1;i<=n;i++){
LD tmp = sqrt(u*u*ans[i]*ans[i]-w[i]*w[i]);
ret += tmp+v[i]*ans[i];
}
return (double)sqrt(ret*ret+disx*disx);
}

int main(){
freopen("river.in","r",stdin);
freopen("river.out","w",stdout);
scanf("%d",&n); cin>>u>>t;
for (int i=1;i<=n;i++) cin>>w[i]>>v[i],
disx+=w[i], MXv=max(MXv,v[i]);
if (disx/u > t) {printf("-1\n");exit(0);}

LD l=u+MXv,r=1e12,mid;
while (r-l > EPS){
mid = (l+r)/2.0;
if (cal(mid) < t) r = mid;
else l = mid;
}

printf("%.3lf\n",GetAns());
for (int i=1;i<=n;i++) printf("%.3lf ",(double)ans[i]);
return 0;
}