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;
}