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

Download