Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <utility>
using namespace std;

int clockwise(int x, int y, int xx, int yy, int xxx, int yyy)
{
    return 1LL * (x - xx) * (y + yy) + 1LL * (xx - xxx) * (yy + yyy) + 1LL * (xxx - x) * (yyy + y) < 0;
}

int main()
{
    int n, hullX[100100], hullY[100100], yIntercept[100100], H = 0, y;

    cin >> n;
    for (int x = 1; x <= n; x++)
    {
        scanf("%d", &y);
        while (H > 1 && clockwise(x, y, hullX[H - 1], hullY[H - 1], hullX[H - 2], hullY[H - 2]))
            H--;
        hullX[H] = x; hullY[H++] = y;
    }

    for (int i = 0; i + 1 < H; i++)
    {
        double slope = 1.0 * (hullY[i] - hullY[i + 1]) / (hullX[i] - hullX[i + 1]);
        yIntercept[i] = int(hullY[i] - slope * hullX[i] + 1e-8);
    }
    yIntercept[H - 1] = 1000111222;

    cin >> n;
    while (n--)
    {
        scanf("%d", &y);
        int i = lower_bound(yIntercept, yIntercept + H, y) - yIntercept;
        double slope = 1.0 * (hullY[i] - y) / hullX[i];
        printf("%.6lf\n", 1 / slope);
    }
}

Code mẫu của happyboy99x

#include<cstdio>

#define long long long

struct Line {
    long a, b, lim;

    Line(long a = 0, long b = 0, long lim = 0):
        a (a), b (b), lim (lim) {}

    double val(long x) const {
        return 1. * (a - x) / b;
    }

    long xCut(const Line &x) const {
        return (a * x.b - b * x.a) / (x.b - b);
    }

    bool bad(const Line &x, const Line &y) const {
        return (a*x.b - b*x.a) * (y.b-b) >= (a*y.b - b*y.a) * (x.b-b);
    }
};

const int N = 1e5, INF = 2e9;
Line l[N];
int nLine;

void addLine(const Line &a) {
    while(nLine > 1 && l[nLine-2].bad(l[nLine-1], a)) --nLine;
    if(nLine > 0) l[nLine-1].lim = l[nLine-1].xCut(a);
    l[nLine++] = a;
}

void enter() {
    int n; scanf("%d", &n);
    for(int i = 0; i < n; ++i) {
        int a; scanf("%d", &a);
        addLine(Line(a, i + 1, INF));
    }
}

void solve() {
    int m; scanf("%d", &m);
    for(int i = 0; i < m; ++i) {
        int s; scanf("%d", &s);
        int low = 0, high = nLine - 1;
        while(low < high) {
            int mid = (low + high) >> 1;
            if(l[mid].lim < s) low = mid + 1;
            else high = mid;
        }
        printf("%.6lf\n", 1 / l[low].val(s));
    }
}

int main() {
    enter();
    solve();
    return 0;
}

Code mẫu của ladpro98

#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, a, b) for(int i = (a); i <=(b); i++)
#define FORD(i, a, b) for(int i = (a); i > (b); i--)
#define REPD(i, a, b) for(int i = (a); i >=(b); i--)
#define TR(it, a) for(typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define SZ(a) (int((a).size()))
#define ALL(a) (a).begin(), (a).end()
#define PB push_back
#define MP make_pair
#define LL long long
#define LD long double
#define II pair<LL, LL>
#define X first
#define Y second
#define VI vector<int>
const int N = 100005;
using namespace std;

void operator -= (II &a, II b) {a.X -= b.X; a.Y -= b.Y;}
bool ccw(II a, II b, II c) {c -= b; b -= a; return b.X * c.Y >= b.Y * c.X;}
vector<II> hull;
II a[N], s[N];
double ans[N];
int n, m;

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> m;
    FOR(i, 0, m) {
        cin >> a[i].Y;
        a[i].X = i + 1;
    }
    sort(a, a + m);
    #define nn (int(hull.size()))
    FOR(i, 0, m) {
        while (nn > 1 && ccw(hull[nn - 2], hull[nn - 1], a[i])) hull.pop_back();
        hull.PB(a[i]);
    }
    cin >> n;
    FOR(i, 0, n) {
        cin >> s[i].X;
        s[i].Y = i;
    }
    sort(s, s + n);
    int j = 0;
    FOR(i, 0, n) {
        while (j + 1 < nn && ccw(MP(0, s[i].X), hull[j], hull[j + 1])) j++;
        ans[s[i].Y] = (double)hull[j].X / (hull[j].Y - s[i].X);
    }
    FOR(i, 0, n) cout << setprecision(6) << fixed << ans[i] << '\n';
    return 0;
}

Code mẫu của hieult

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iomanip>
#include <iostream>
#include <algorithm>

#include <ctime>
#include <deque>
#include <bitset>
#include <cctype>
#include <utility>
#include <cassert>

using namespace std;

typedef long long ll;
typedef double ld;
typedef unsigned int ui;
typedef unsigned long long ull;

#define Rep(i,n) for(int i = 0; i < (n); ++i)
#define Repd(i,n) for(int i = (n)-1; i >= 0; --i)
#define For(i,a,b) for(int i = (a); i <= (b); ++i)
#define Ford(i,a,b) for(int i = (a); i >= (b); --i)
//#define Fit(i,v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i)
//#define Fitd(i,v) for(__typeof((v).rbegin()) i = (v).rbegin(); i != (v).rend(); ++i)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()
#define ms(a,x) memset(a, x, sizeof(a))

template<class F, class T> T convert(F a, int p = -1) { stringstream ss; if (p >= 0) ss << fixed << setprecision(p); ss << a; T r; ss >> r; return r; }
template<class T> T gcd(T a, T b) { T r; while (b != 0) { r = a % b; a = b; b = r; } return a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T> T sqr(T x) { return x * x; }
template<class T> T cube(T x) { return x * x * x; }
template<class T> int getbit(T s, int i) { return (s >> i) & 1; }
template<class T> T onbit(T s, int i) { return s | (T(1) << i); }
template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); }
template<class T> int cntbit(T s) { return s == 0 ? 0 : cntbit(s >> 1) + (s & 1); }

const int bfsz = 1 << 16;
char bf[bfsz + 5];
int rsz = 0;
int ptr = 0;
char gc() {
    if (rsz <= 0) {
        ptr = 0;
        rsz = (int) fread(bf, 1, bfsz, stdin);
        if (rsz <= 0)
            return EOF;
    }
    --rsz;
    return bf[ptr++];
}
void ga(char &c) {
    c = EOF;
    while (!isalpha(c))
        c = gc();
}
int gs(char s[]) {
    int l = 0;
    char c = gc();
    while (isspace(c))
        c = gc();
    while (c != EOF && !isspace(c)) {
        s[l++] = c;
        c = gc();
    }
    s[l] = '\0';
    return l;
}
template<class T> bool gi(T &v) {
    v = 0;
    char c = gc();
    while (c != EOF && c != '-' && !isdigit(c))
        c = gc();
    if (c == EOF)
        return false;
    bool neg = c == '-';
    if (neg)
        c = gc();
    while (isdigit(c)) {
        v = v * 10 + c - '0';
        c = gc();
    }
    if (neg)
        v = -v;
    return true;
}

typedef pair<int, int> II;

const ld PI = acos(-1.0);
const ld eps = 1e-9;

const int dr[] = {0, +1, 0, -1};
const int dc[] = {+1, 0, -1, 0};

const int inf = (int)1e9 + 5;
const ll linf = (ll)1e16 + 5;
const ll mod = (ll)1e9 + 7;

#define maxn 100005

int cmp(ll x, ll y){
    if(x == y) return 0;
    return x < y ? -1 : 1;
}

struct Point {
    ll x, y;
    Point(){};
    Point(ll _x, ll _y){
        x = _x; y = _y;
    }
    bool operator ==(const Point& that) const {
        return (cmp(x, that.x) == 0 && cmp(y, that.y) == 0);
    }
    bool operator <(const Point& that) const {
        if (cmp(x, that.x) != 0) return cmp(x, that.x) < 0;
        return cmp(y, that.y) < 0;
    }
};

ll sqrdist(Point P0, Point P1){
    return sqr(P0.x - P1.x) + sqr(P0.y - P1.y);
}

int ccw(Point p0, Point p1, Point p2) {
    ll dx1 = p1.x - p0.x, dy1 = p1.y - p0.y;
    ll dx2 = p2.x - p0.x, dy2 = p2.y - p0.y;
    return cmp(dx1 * dy2 - dx2 * dy1, 0);
}

Point O;
bool cmp_angle(Point P1, Point P2) {
    int ret = ccw(O, P1, P2);
    if (ret != 0) return ret > 0;
    return sqrdist(O, P1) < sqrdist(O, P2);
}

int convex_hull(Point a[], int n) {
    if (n <= 3) return n;

    int imin = 0;
    Rep(i, n) if (a[i].y < a[imin].y || (a[i].y == a[imin].y && a[i].x < a[imin].x)) imin = i;

    swap(a[imin], a[0]);
    O = a[0];
    sort(a + 1, a + n, cmp_angle);

    int m = 2;
    For(i, 2, n - 1) {
        while (m > 1 && ccw(a[i], a[m - 1], a[m - 2]) >= 0) --m;
        swap(a[m], a[i]);
        ++m;
    }

    return m;
}


int n, m, x;
II S[maxn];
ld res[maxn];
Point P[maxn * 2];

ld cal(ll h, int id){
    ld res = P[id].x * (ld)(1.0) / (P[id].y - h);
    if(h >= P[id].y) res = linf - P[id].y;
    return res;
}

int  main()
{
//  freopen("in.txt", "r", stdin);

    cin >> n;
    Rep(i, n){
        scanf("%d", &x);
        P[i] = Point(i + 1, x);
    }

    n = convex_hull(P, n);
    For(i, n, n + n) P[i] = P[i - n];

    cin >> m;
    S[0] = mp(0, 0);
    For(i, 1, m){
        scanf("%d", &S[i].fi);
        S[i].se = i;
    }
    sort(S + 1, S + m + 1);

    Rep(i, n / 2) swap(P[i], P[n - 1 - i]);

    ll MIN = linf;
    int run = -1;
    Rep(i, n) if(cal(0, i) < MIN){
        MIN = cal(0, i);
        run = i;
    }

    For(i, 1, m){
        while(cal(S[i].fi, run) > cal(S[i].fi, run + 1)) run++;
        res[S[i].se] = cal(S[i].fi, run);
    }

    For(i, 1, m){
        printf("%.6lf\n", res[i]);
    }
     // getch();
}

Code mẫu của skyvn97

#include<bits/stdc++.h>
#define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1)
#define REP(i,n) for (int i=0;i<(n);i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
#define fi   first
#define se   second
using namespace std;
const double INF=1e9+7;
const double eps=1e-7;
typedef pair<double,double> dd;
bool cmp(const dd &a,const dd &b) {
        return (a.fi<b.fi);
}
class ConvexHull {
    private:
    vector<dd> v;
    double L,R;
    int sz;
    bool empty;
    public: 
    ConvexHull() {
        L=0.0;R=0.0;sz=0;empty=true;
    }
    ConvexHull(double l,double r,int n) {
        L=l;R=r;
        empty=true;
        v=vector<dd>(2*n+7);
        sz=2;
        v[0]=dd(L,0.0);
        v[1]=dd(R,0.0);
    }
    void addline(double a,double b) {       
        if (empty) {
            v[0]=dd(L,a*L+b);
            v[1]=dd(R,a*R+b);
            empty=false;
            return;
        }
        int i;
        for (i=sz-1;i>=0;i=i-1) if (v[i].se>a*v[i].fi+b+eps) break;
        if (i==sz-1) return;
        if (i<0) {
            v[0]=dd(L,a*L+b);
            v[1]=dd(R,a*R+b);
            sz=2;
            return;
        }
        double a2=(v[i+1].se-v[i].se)/(v[i+1].fi-v[i].fi);
        double b2=v[i].se-a2*v[i].fi;
        double x=-(b2-b)/(a2-a);
        v[i+1]=dd(x,a*x+b);
        v[i+2]=dd(R,a*R+b);
        sz=i+3;     
    }
    double getmax(double x) const {     
        int p=lower_bound(v.begin(),v.begin()+sz,dd(x-eps,x-eps),cmp)-v.begin();
        if (p<1) p=1;       
        double a=(v[p].se-v[p-1].se)/(v[p].fi-v[p-1].fi);
        double b=v[p].se-a*v[p].fi;
        return (a*x+b);
    }
};
ConvexHull CH;
int n,m;
void process(void) {
    scanf("%d",&n); 
    CH=ConvexHull(0.0,INF,n);
    vector<dd> line;
    line.push_back(dd(0.0,0.0));
    FOR(i,1,n) {
        int t;
        scanf("%d",&t);
        line.push_back(dd(-1.0/i,1.0*t/i));     
    }
    sort(line.begin(),line.end());
    FORE(it,line) CH.addline(it->fi,it->se);
    scanf("%d",&m);
    REP(i,m) {
        int s;
        scanf("%d",&s);
        printf("%.6lf\n",1.0/CH.getmax(s));
    }
}
int main(void) {
    process();
    return 0;
}