NKSPILJA - Hang động
Tác giả: khuc_tuan
Ngôn ngữ: C++
#include <iostream>
using namespace std;
struct Point {
int x, y;
Point() {}
Point(int x,int y) : x(x), y(y) {}
};
int n;
Point a[5050];
bool checkok(double Y) {
double lower = a[0].x, upper = a[n-1].x;
for(int i=0;i+1<n;++i) {
// a[i] -> a[i+1]
if(a[i].y==a[i+1].y) {
if(a[i].y > Y) return false;
}
else {
double X = (Y - a[i+1].y) * (a[i+1].x - a[i].x) / (a[i+1].y - a[i].y) + a[i+1].x;
if(a[i+1].y>a[i].y) upper = min( upper, X);
else lower = max( lower, X);
}
}
return lower <= upper;
}
int main() {
scanf("%d", &n);
for(int i=0;i<n;++i)
scanf("%d%d", &a[i].x, &a[i].y);
double left = 0, right = 1000000;
for(int kk=0;kk<50;++kk) {
double mid = (left+right) / 2;
if(checkok(mid)) right = mid;
else left = mid;
}
printf("%.2f\n", left);
return 0;
}