Codeforces Round #365 (Div. 2) C - Chris and Road 二分找切点

 // Codeforces Round #365 (Div. 2)
// C - Chris and Road 二分找切点
// 题意:给你一个凸边行,凸边行有个初始的速度往左走,人有最大速度,可以停下来,竖直走。
// 问走到终点的最短时间
// 思路:
// 1.贪心来做
// 2.我觉的二分更直观
// 可以抽象成:一条射线与凸边行相交,判断交点。二分找切点 #include <bits/stdc++.h>
using namespace std;
#define LL long long
const int inf = 0x3f3f3f3f;
const int MOD =;
const int N =1e6+;
#define clc(a,b) memset(a,b,sizeof(a))
const double eps = 1e-;
struct Point{
double x,y;
Point(){}
Point(int x_,int y_):x(x_),y(y_){}
Point operator + (const Point &t)const{
return Point(x+t.x,y+t.y);
}
Point operator - (const Point &t)const{
return Point(x-t.x,y-t.y);
}
double operator * (const Point &t)const{
return x*t.y-y*t.x;
}
double operator ^ (const Point &t)const{
return x*t.x+y*t.y;
}
bool operator < (const Point & a) const{
if(x==a.x) return y>a.y;
return x<a.x;
}
}p[]; int n;
bool judge(double k,double b){
int tot=,cnt=;
for(int i=;i<=n;i++){
if(k*p[i].x+b-p[i].y<) tot++;
else cnt++;
if(cnt&&tot) return false;
}
return true;
}
int main(){
int w;
double v,u;
scanf("%d%d%lf%lf",&n,&w,&v,&u);
for(int i=;i<=n;i++){
scanf("%lf%lf",&p[i].x,&p[i].y);
}
double k=u/v;
if(judge(k,0.0)){
printf("%.8f\n",(double)(w/u));
}
else{
double l=,r=1e9;
double ans;
while(r-l>eps){
double mid = (l+r)/2.0;
if(judge(k,-mid/v*u)){
ans=(double)(w/u)+mid/v;
r=mid;
}
else{
l=mid;
}
}
printf("%.8f\n",ans);
}
return ;
}
上一篇:Linux之vi编辑器的使用


下一篇:Codeforces Round #524 (Div. 2) F. Katya and Segments Sets(主席树)