#include #include #include #include using namespace std ; using pt = pair ; // is the middle point below the a--b segment? int interplow(const pt &a, const pt &b, const pt &c) { double delta { c.first - a.first } ; if (delta == 0) return b.second < a.second || b.second < c.second ; double y { (a.second * (c.first - b.first) + c.second * (b.first - a.first)) / delta } ; return b.second < y ; } int main(int argc, char *[]) { cout << setprecision(2) << fixed ; int N { 0 } ; double budget { 0 } ; cin >> N >> budget ; vector pts ; pts.push_back(make_pair(0, 0)) ; for (int i=0; i> cost >> health >> potency ; pts.push_back(make_pair(budget*health/cost, budget*potency/cost)) ; } sort(pts.begin(), pts.end()) ; double r {0} ; for (int i=1; i 1) cout << "Stupid solution: " << r << endl ; int wr {1} ; for (int i=1; i<(int)pts.size(); i++) { while (wr > 1 && interplow(pts[wr-2], pts[wr-1], pts[i])) wr-- ; pts[wr++] = pts[i] ; } for (int i=1; i+1 pts[i].first && bx < pts[i+1].first) { double by = (c - a * bx) / b ; r = max(r, bx*by) ; } } } cout << r << endl ; }