fork(1) download 
  1. /* Author haleyk10198 */
  2. /* 作者:  haleyk10198 */
  3. #include <iostream>
  4. #include <fstream>
  5. #include <sstream>
  6. #include <cstdlib>
  7. #include <cstdio>
  8. #include <vector>
  9. #include <map>
  10. #include <queue>
  11. #include <cmath>
  12. #include <algorithm>
  13. #include <cstring>
  14. #include <iomanip>
  15. #include <ctime>
  16. #include <string>
  17. #include <set>
  18. #include <stack>
  19.  
  20. #define MOD 1000000007
  21. #define INF 2147483647
  22. #define PI 3.1415926535897932384626433
  23. #define ll long long
  24. #define pii pair<int,int>
  25. #define mp(x,y) make_pair((x),(y))
  26.  
  27. using namespace std;
  28.  
  29. struct edge{
  30. 	double a,b,c,m;
  31. 	pii u,v;
  32. 	edge(pii e,pii f):u(e),v(f){
  33. 		if(e.first==f.first){
  34. 			a=1;b=0;c=e.second;
  35. 			m=-2e9;
  36. 		}
  37. 		else{
  38. 			m=1.0*(e.second-f.second)/(e.first-f.first);
  39. 			b=-1;a=m;c=e.second-m*e.first;
  40. 		}
  41. 	}
  42. };
  43.  
  44. int n,w,v,u;
  45. vector<edge> a;
  46. vector<pii> list;
  47.  
  48. bool check(void){
  49. 	double mid=1.0*w/u;
  50. 	edge now=edge(mp(0,0),mp(mid*v,w));
  51. 	bool f=true;
  52. 	for(auto x:a){/*
  53. 		double x1,y1;
  54. 		if(x.a==now.a||x.b==0)
  55. 			continue;
  56. 		if(x.m==2e9){
  57. 			x1=x.u.first;
  58. 			y1=(x1*now.a+now.c)/(-now.b);
  59. 		}
  60. 		else{
  61. 			x1=1.0*(x.c-now.c)/(now.a-x.a);
  62. 			y1=-1.0*(x.a*x1+x.c)/x.b;
  63. 		}
  64. 		if((x1<x.u.first)^(x1<x.v.first)&&(y1<x.u.second)^(y1<x.v.second))
  65. 			f=false;
  66. 		*/
  67. 		double x1=x.u.first,y1=x.u.second;
  68. 		if(x1/v<y1/u)
  69. 			f=false;
  70. 	}
  71. 	return f;
  72. }
  73.  
  74. /*
  75. double bins(double l,double r,int cnt){
  76. 	double mid=(l+r)/2;
  77. 	if(cnt==100)
  78. 		return mid;
  79. 	if(!check(mid))
  80. 		return bins(mid,r,cnt+1);
  81. 	else
  82. 		return bins(l,mid,cnt+1);
  83. }
  84. */
  85.  
  86. int main(){
  87. 	//freopen("input.txt","r",stdin);
  88. 	//freopen("output.txt","w",stdout);
  89. 	//ios_base::sync_with_stdio(false);
  90. 	cin>>n>>w>>v>>u;
  91. 	int low,lowv=INF;
  92. 	for(int i=0;i<n;i++){
  93. 		int x,y;
  94. 		cin>>x>>y;
  95. 		list.push_back(mp(x,y));
  96. 	}
  97. 	for(int i=0;i<n;i++){
  98. 		a.push_back(edge(list[i],list[(i+1)%n]));
  99. 		if(lowv>a[i].u.second){
  100. 			low=i;
  101. 			lowv=a[i].u.second;
  102. 		}
  103. 	}
  104. 	if(check()||lowv>w)
  105. 		cout<<fixed<<setprecision(12)<<1.0*w/u;
  106. 	else{
  107. 		int nowy=0,i=low;
  108. 		double t=0.0;
  109. 		t=max(1.0*a[i].u.second/u,1.0*a[i].u.first/v);
  110. 		nowy=a[i].u.second;
  111. 		for(;a[i].m>0;(++i)%=n){
  112. 			t=max(1.0*(a[i].v.second-nowy)/u+t,1.0*a[i].v.first/v);
  113. 			nowy=a[i].v.second;
  114. 		}
  115. 		t+=1.0*(w-nowy)/u;
  116. 		cout<<fixed<<setprecision(12)<<t<<endl;
  117. 	}
  118. 	return 0;
  119. }
  120.  
Success #stdin #stdout 0s 3464KB
comments (?)
stdin 
5 5 1 2
1 2
3 1
4 3
3 4
1 4
stdout 
5.000000000000
https://ideone.com/mFVRYD
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!