<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

278. Fuel
Time limit per test: 0.5 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



A fuel station has infinite amount of each of N kinds of fuel. Each kind of fuel has density ai, cost bi and intensity ci. m kilograms of such fuel has volume mai, intensity mci and costs mbi dollars. Your car can store any mixture of different kinds of fuel such that the overall volume does not exceed A. You have B dollars. Your task is to determine the maximal overall intensity of the fuel you can buy. Note that you can buy any nonnegative amount of any kind of fuel, not necessarily an integer number of kilograms.

Input
The first line of the input contains three integers N, A, B (1≤ N≤ 75000, 1≤ A,B≤ 1000). Each of the next N lines describes one kind of fuel. i+1-st line contains three integers ai, bi, ci (0i,bi,ci≤ 100).

Output
The only line of the output must contain single number with at least 6 digits after the decimal point, being the maximal overall intensity.

Example(s)
sample input
sample output
2 1 1 
1 2 6
2 1 6
4.000000



Novosibirsk SU Contest #2, by Novosibirsk Team #1

<|response|>
1. Abridged Problem Statement  
You have N types of fuel. Fuel i has density aᵢ, cost bᵢ, and intensity cᵢ per kilogram. If you buy mᵢ kilograms of fuel i, it occupies volume aᵢ·mᵢ, costs bᵢ·mᵢ dollars, and contributes intensity cᵢ·mᵢ. You have two resource limits: total volume ≤ A and total money ≤ B, and you may choose real (non‐integer) quantities mᵢ ≥ 0. Maximize the total intensity ∑ cᵢ·mᵢ.

2. Key Observations  
- This is a linear program with two constraints (volume and cost) and nonnegative variables mᵢ. By standard LP theory, an optimal solution lies at a vertex of the feasible polyhedron—here that means you either use exactly one fuel type, or mix exactly two types.  
- Define M = total intensity = ∑ cᵢ·mᵢ. Introduce weights xᵢ ≥ 0 with ∑xᵢ=1, and set mᵢ = (M·xᵢ)/cᵢ. Then the resource constraints become  
    ∑ aᵢ·mᵢ = M·∑(aᵢ/cᵢ)·xᵢ ≤ A  
    ∑ bᵢ·mᵢ = M·∑(bᵢ/cᵢ)·xᵢ ≤ B  
  Denote points pᵢ = (Xᵢ, Yᵢ) = (aᵢ/cᵢ, bᵢ/cᵢ). Any convex combination P = ∑xᵢpᵢ lies in the convex hull of {pᵢ}. The inequalities become  
    M·P.x ≤ A, M·P.y ≤ B  ⇒  M ≤ min(A/P.x, B/P.y).  
  To maximize M we want to minimize t = max(P.x/A, P.y/B) over P in the convex hull. Geometrically, that is the scaling factor t so that the ray from the origin through (A,B) first touches the convex hull of the pᵢ.  
- Therefore:  
  1. Check each single point pᵢ alone: Mᵢ = min(A/(aᵢ/cᵢ), B/(bᵢ/cᵢ)).  
  2. Build the convex hull of all pᵢ in the plane.  
  3. For each edge [pⱼ,pₖ] of the hull, compute its intersection I with the ray from (0,0) towards (A,B). If I lies on the segment, evaluate M = min(A/I.x, B/I.y).  
  4. The maximum over all these candidates is the answer.

3. Full Solution Approach  
1. Read N, A, B.  
2. For each fuel i:  
   - Compute Xᵢ = aᵢ/cᵢ and Yᵢ = bᵢ/cᵢ.  
   - Track answer = max(answer, min(A/Xᵢ, B/Yᵢ)).  
   - Store point pᵢ = (Xᵢ, Yᵢ).  
3. Sort the points by (x,y), remove duplicates (within an eps).  
4. Build the convex hull by the monotone‐chain algorithm in O(N log N).  
5. Let O = (0,0), T = (A,B). For each consecutive hull vertices pⱼ, pₖ:  
   - If the line OT is not parallel to line pⱼpₖ, compute their intersection I by solving two‐line intersection.  
   - If I lies between pⱼ and pₖ (within an eps), compute M = min(A/I.x, B/I.y) and update answer.  
6. Print answer with six decimal places.

4. C++ Solution
```cpp
#include <bits/stdc++.h>
// #include <coding_library/geometry/geometry2d.hpp>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

using coord_t = long double;

struct Point {
    static constexpr coord_t eps = 1e-9;

    coord_t x, y;
    Point(coord_t x = 0, coord_t y = 0) : x(x), y(y) {}

    Point operator+(const Point& p) const { return Point(x + p.x, y + p.y); }
    Point operator-(const Point& p) const { return Point(x - p.x, y - p.y); }
    Point operator*(coord_t c) const { return Point(x * c, y * c); }
    Point operator/(coord_t c) const { return Point(x / c, y / c); }

    coord_t operator*(const Point& p) const { return x * p.x + y * p.y; }
    coord_t operator^(const Point& p) const { return x * p.y - y * p.x; }

    bool operator==(const Point& p) const { return x == p.x && y == p.y; }
    bool operator!=(const Point& p) const { return x != p.x || y != p.y; }
    bool operator<(const Point& p) const {
        return x != p.x ? x < p.x : y < p.y;
    }
    bool operator>(const Point& p) const {
        return x != p.x ? x > p.x : y > p.y;
    }
    bool operator<=(const Point& p) const {
        return x != p.x ? x < p.x : y <= p.y;
    }
    bool operator>=(const Point& p) const {
        return x != p.x ? x > p.x : y >= p.y;
    }

    coord_t norm2() const { return x * x + y * y; }
    double norm() const { return sqrt(norm2()); }
    double angle() const { return atan2(y, x); }

    Point rotate(double a) const {
        return Point(x * cos(a) - y * sin(a), x * sin(a) + y * cos(a));
    }

    Point perp() const { return Point(-y, x); }
    Point unit() const { return *this / norm(); }
    Point normal() const { return perp().unit(); }
    Point project(const Point& p) const {
        return *this * (*this * p) / norm2();
    }
    Point reflect(const Point& p) const {
        return *this * 2 * (*this * p) / norm2() - p;
    }

    friend ostream& operator<<(ostream& os, const Point& p) {
        return os << p.x << ' ' << p.y;
    }
    friend istream& operator>>(istream& is, Point& p) {
        return is >> p.x >> p.y;
    }

    friend int ccw(const Point& a, const Point& b, const Point& c) {
        coord_t v = (b - a) ^ (c - a);
        if(-eps <= v && v <= eps) {
            return 0;
        } else if(v > 0) {
            return 1;
        } else {
            return -1;
        }
    }

    friend bool point_on_segment(
        const Point& a, const Point& b, const Point& p
    ) {
        return ccw(a, b, p) == 0 && p.x >= min(a.x, b.x) - eps &&
               p.x <= max(a.x, b.x) + eps && p.y >= min(a.y, b.y) - eps &&
               p.y <= max(a.y, b.y) + eps;
    }

    friend bool point_in_triangle(
        const Point& a, const Point& b, const Point& c, const Point& p
    ) {
        int d1 = ccw(a, b, p);
        int d2 = ccw(b, c, p);
        int d3 = ccw(c, a, p);
        return (d1 >= 0 && d2 >= 0 && d3 >= 0) ||
               (d1 <= 0 && d2 <= 0 && d3 <= 0);
    }

    friend Point line_line_intersection(
        const Point& a1, const Point& b1, const Point& a2, const Point& b2
    ) {
        return a1 +
               (b1 - a1) * ((a2 - a1) ^ (b2 - a2)) / ((b1 - a1) ^ (b2 - a2));
    }
};

class Polygon {
  public:
    vector<Point> points;

    Polygon() {}
    Polygon(const vector<Point>& points) : points(points) {}

    int size() const { return points.size(); }

    coord_t area() const {
        coord_t a = 0;
        for(int i = 0; i < size(); i++) {
            a += points[i] ^ points[(i + 1) % size()];
        }
        return a / 2.0;
    }
};

class ConvexHull : public Polygon {
  public:
    int upper_hull_size;

    ConvexHull(const vector<Point>& points) {
        this->points = points;
        sort(this->points.begin(), this->points.end());
        this->points.erase(
            unique(this->points.begin(), this->points.end()), this->points.end()
        );

        if(this->points.size() <= 2) {
            this->upper_hull_size = this->points.size();
            return;
        }

        vector<int> hull = {0};
        vector<bool> used(this->points.size());

        function<void(int, int)> expand_hull = [&](int i, int min_hull_size) {
            while((int)hull.size() >= min_hull_size &&
                  ccw(this->points[hull[hull.size() - 2]],
                      this->points[hull.back()], this->points[i]) >= 0) {
                used[hull.back()] = false;
                hull.pop_back();
            }
            hull.push_back(i);
            used[i] = true;
        };

        for(int i = 1; i < (int)this->points.size(); i++) {
            expand_hull(i, 2);
        }

        upper_hull_size = hull.size();
        for(int i = (int)this->points.size() - 2; i >= 0; i--) {
            if(!used[i]) {
                expand_hull(i, upper_hull_size + 1);
            }
        }

        hull.pop_back();

        vector<Point> points_in_hull;
        for(int i: hull) {
            points_in_hull.push_back(this->points[i]);
        }
        this->points = std::move(points_in_hull);
    }
};

int n;
coord_t A, B;
vector<tuple<int, int, int>> fuels;

void read() {
    cin >> n >> A >> B;
    fuels.resize(n);
    for(auto& [x, y, z]: fuels) {
        cin >> x >> y >> z;
    }
}

void solve() {
    // Each fuel kind i is a point p_i = (a_i/c_i, b_i/c_i): per unit of
    // intensity it uses p_i.x of volume and p_i.y of dollars. A mixture is a
    // convex combination of these points scaled by the total intensity t, so
    // the resource cost per unit intensity ranges over the convex hull of the
    // points. For a hull point p the largest feasible intensity is
    // min(A / p.x, B / p.y).
    //
    // - The optimum over the whole feasible region is attained either at an
    //   original vertex or where the ray from the origin through (A, B) crosses
    //   a hull edge, since that direction balances the two constraints.
    //
    // - So we build the convex hull of the points, evaluate min(A/x, B/y) at
    //   every vertex, and also at the intersection of segment origin-(A,B) with
    //   each hull edge, taking the maximum.

    coord_t ans = 0.0;
    vector<Point> points;
    for(int i = 0; i < n; i++) {
        points.push_back(Point(
            get<0>(fuels[i]) / (coord_t)get<2>(fuels[i]),
            get<1>(fuels[i]) / (coord_t)get<2>(fuels[i])
        ));
        ans = max(ans, min(A / points[i].x, B / points[i].y));
    }

    ConvexHull hull(points);

    Point origin(0, 0), target_loc(A, B);
    for(int i = 0; i < (int)hull.points.size(); i++) {
        Point p1 = hull.points[i];
        Point p2 = hull.points[(i + 1) % hull.points.size()];

        if(fabs((target_loc - origin) ^ (p1 - p2)) > Point::eps) {
            Point intersection =
                line_line_intersection(origin, target_loc, p1, p2);
            if(point_on_segment(p1, p2, intersection)) {
                ans = max(ans, min(A / intersection.x, B / intersection.y));
            }
        }
    }

    cout << setprecision(6) << fixed << ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5. Python Implementation with Detailed Comments  
```python
import sys

def main():
    data = sys.stdin.read().split()
    it = iter(data)
    N = int(next(it))
    A = float(next(it))
    B = float(next(it))

    pts = []
    answer = 0.0

    # 1) Read fuels, compute (a/c, b/c), track single-fuel best
    for _ in range(N):
        a = float(next(it))
        b = float(next(it))
        c = float(next(it))
        X = a / c
        Y = b / c
        if X > 0 and Y > 0:
            M0 = min(A/X, B/Y)
            if M0 > answer:
                answer = M0
        pts.append((X, Y))

    # 2) Sort and remove duplicates
    pts = sorted(set(pts))
    # 3) Convex hull (monotone chain)
    def cross(o, a, b):
        return (a[0]-o[0])*(b[1]-o[1]) - (a[1]-o[1])*(b[0]-o[0])

    if len(pts) > 1:
        lower = []
        for p in pts:
            while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
                lower.pop()
            lower.append(p)
        upper = []
        for p in reversed(pts):
            while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
                upper.pop()
            upper.append(p)
        hull = lower[:-1] + upper[:-1]
    else:
        hull = pts

    O = (0.0, 0.0)
    T = (A, B)

    # 4) For each hull edge, find intersection with ray O->T
    def intersect(O, T, P, Q):
        # Solve O + t*(T-O) = P + u*(Q-P)
        ox, oy = O; tx, ty = T
        px, py = P; qx, qy = Q
        dx1 = tx - ox; dy1 = ty - oy
        dx2 = qx - px; dy2 = qy - py
        denom = dx1*dy2 - dy1*dx2
        if abs(denom) < 1e-15:
            return None
        num   = (px - ox)*dy2 - (py - oy)*dx2
        t     = num / denom
        return (ox + t*dx1, oy + t*dy1)

    def on_segment(P, Q, R):
        return min(P[0],Q[0]) - 1e-9 <= R[0] <= max(P[0],Q[0]) + 1e-9 \
           and min(P[1],Q[1]) - 1e-9 <= R[1] <= max(P[1],Q[1]) + 1e-9

    H = len(hull)
    for i in range(H):
        P1 = hull[i]
        P2 = hull[(i+1)%H]
        I = intersect(O, T, P1, P2)
        if I and on_segment(P1, P2, I) and I[0] > 0 and I[1] > 0:
            M1 = min(A/I[0], B/I[1])
            if M1 > answer:
                answer = M1

    # 5) Output with six decimals
    print(f"{answer:.6f}")

if __name__ == "__main__":
    main()
```

Explanation of Key Steps:  
- We map each fuel to a 2D point (volume‐per‐intensity, cost‐per‐intensity).  
- Any mixture corresponds to a convex combination of these points, and the maximum intensity M is the reciprocal of the minimal scaling needed to fit that convex combination under both resource limits.  
- Geometric intersection with the ray from the origin through (A,B) finds the critical mixture of two fuels.  
- We also test pure fuels directly. This yields an O(N log N) solution, efficient for N up to 75 000.