fork download 
  1. #include <bits/stdc++.h>
  2. #define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; ++i)
  3. #define fi first
  4. #define se second
  5. #define el "\n"
  6. #define pb push_back
  7. #define sz(a) (int)(a).size()
  8. #define FILL(a,x) memset(a,x,sizeof(a))
  9. using namespace std;
  10. typedef long long ll;
  11. typedef pair<int,int> ii;
  12. const int N = 1000003;
  13.  
  14. struct P{ long double x,y; };
  15.  
  16. static inline long double cross(const P& a, const P& b, const P& c){
  17. return (b.x-a.x)*(c.y-b.y)-(b.y-a.y)*(c.x-b.x);
  18. }
  19.  
  20. int main(){
  21. ios::sync_with_stdio(false);
  22. cin.tie(nullptr); cout.tie(nullptr);
  23.  
  24. int n; long double M;
  25. if(!(cin>>n>>M)) return 0;
  26. vector<P> v; v.reserve(n);
  27. FOR(i,1,n){
  28. long double w,a,b; cin>>w>>a>>b;
  29. long double x=a/w, y=b/w;
  30. if(x>0 || y>0) v.pb({x,y});
  31. }
  32. if(M==0 || v.empty()){
  33. cout.setf(std::ios::fixed); cout<<setprecision(2)<<0.0<<el;
  34. return 0;
  35. }
  36. sort(v.begin(), v.end(), [](const P& A, const P& B){
  37. if(A.x==B.x) return A.y>B.y;
  38. return A.x<B.x;
  39. });
  40. vector<P> u; u.reserve(sz(v));
  41. for(int i=0;i<sz(v);++i){
  42. if(u.empty() || v[i].x!=u.back().x) u.pb(v[i]);
  43. else if(v[i].y>u.back().y) u.back().y=v[i].y;
  44. }
  45. vector<P> s; s.reserve(sz(u));
  46. for(int i=0;i<sz(u);++i){
  47. while(!s.empty() && s.back().y<=u[i].y) s.pop_back();
  48. s.pb(u[i]);
  49. }
  50. vector<P> h; h.reserve(sz(s));
  51. for(int i=0;i<sz(s);++i){
  52. while(sz(h)>=2 && cross(h[sz(h)-2],h[sz(h)-1],s[i])>=0) h.pop_back();
  53. h.pb(s[i]);
  54. }
  55. long double best=0;
  56. for(int i=0;i<sz(h);++i) if(h[i].x*h[i].y>best) best=h[i].x*h[i].y;
  57. for(int i=0;i+1<sz(h);++i){
  58. long double x1=h[i].x,y1=h[i].y,x2=h[i+1].x,y2=h[i+1].y;
  59. long double dx=x2-x1, dy=y2-y1;
  60. if(dx==0 || dy==0) continue;
  61. long double t=-(x1*dy+y1*dx)/(2*dx*dy);
  62. if(t>0 && t<1){
  63. long double X=x1+t*dx, Y=y1+t*dy;
  64. long double val=X*Y;
  65. if(val>best) best=val;
  66. }
  67. }
  68. long double ans = M*M*best;
  69. cout.setf(std::ios::fixed);
  70. cout<<setprecision(2)<<(double)ans<<el;
  71. return 0;
  72. }
  73.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/2Yp0y6
language:
C++14 (clang 8.0)
created:
6 days 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!