NKSPILJA - Hang động

Tác giả: ladpro98

Ngôn ngữ: C++

#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>
#include <climits>
#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 RESET(a, v) memset((a), (v), sizeof((a)))
#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<int, int>
#define X first
#define Y second
#define VI vector<int>
const int N = 5050;
const double EPS = 1e-9;
using namespace std;

typedef pair<double, double> point;
typedef pair<double, double> line;

bool eq(const double &a, const double &b)
    {return fabs(a - b) < EPS;}
bool eqX(const point &a, const point &b)
    {return eq(a.X, b.X);}

line makeLine(point P, point Q) {
    line tmp;
    tmp.X = (P.Y - Q.Y) / (P.X - Q.X);
    tmp.Y = P.Y - tmp.X * P.X;
    return tmp;
}

double xIntercept(line d1, line d2)
    {return (d2.Y - d1.Y) / (d1.X - d2.X);}
double yIntercept(line d1, line d2){
    double x = xIntercept(d1, d2);
    return d1.X * x + d1.Y;
}

bool bad(line a, line b, line c)
    {return xIntercept(a, b) > EPS + xIntercept(b, c);}
bool cmp(const point &a, const point &b) {
    return !eq(a.X, b.X) ? a.X < b.X : a.Y > b.Y;
}
int n;
point a[N];

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n;
    FOR(i, 0, n) cin >> a[i].X >> a[i].Y;
    vector<line> lines, hull;
    FOR(i, 1, n) lines.PB(makeLine(a[i - 1], a[i]));
    sort(ALL(lines), cmp);
    lines.resize(unique(ALL(lines), eqX) - lines.begin());
    #define nn SZ(hull)
    FOR(i, 0, SZ(lines)) {
        while (nn > 1 && bad(hull[nn - 2], hull[nn - 1], lines[i])) hull.pop_back();
        hull.PB(lines[i]);
    }
    double ans = 1e7;
    FOR(i, 1, nn)
        ans = min(ans, yIntercept(hull[i - 1], hull[i]));
    cout << setprecision(2) << fixed << ans;
    return 0;
}

Download