www.b2bchain.cn

# Airplane Landing Problem

## Problem Description

With human lives at stake, an air traffic controller has to schedule the airplanes that are landing at an airport in order to avoid airplane collision. Each airplane iihas a time window [si,ti][si,ti] during which it can safely land. You must compute the exact time of landing for each airplane that respects these time windows. Furthermore, the airplane landings should be stretched out as much as possible so that the minimum time gap between successive landings is as large as possible.

For example, if the time window of landing three airplanes are [10:00-11:00], [11:20-11:40], [12:00-12:20], and they land at 10:00, 11:20, 12:20 respectively, then the smallest gap is 60 minutes, which occurs between the last two airplanes.

Given 5 time windows, denoted as [s1,t1],[s2,t2],⋯,[s5,t5][s1,t1],[s2,t2],⋯,[s5,t5] satisfying 0<=s1<t1<s2<t2<⋯<s5<t5<=240<=s1<t1<s2<t2<⋯<s5<t5<=24. You are required to give the exact landing time of each airplane, in which the smallest gap between successive landings is maximized.

Notice:

Make sure that each airplane lands as early as possible.

## Input

10 numbers(type is float32) s1,t1,s2,t2,⋯,s5,t5s1,t1,s2,t2,⋯,s5,t5, satisfying 0<=s1<t1<s2<t2<⋯<s5<t5<=240<=s1<t1<s2<t2<⋯<s5<t5<=24.

## Output

5 numbers(type is float32) l1,l2,⋯,l5l1,l2,⋯,l5, with accuracy of two decimal digits.

## Sample Input

1 2 3 4 5 6 7 8 9 10

## Sample Output

1.00 3.25 5.50 7.75 10.00

` `#include <iostream> #include<cmath> #include<vector> using namespace std;  int n, m; double BE, EN; const double eps = 1e-6;   vector<double>  ve;  int dcmp(double x) { 	if (fabs(x)<eps) return 0; 	return x>0 ? 1 : -1; }   bool can(double ans) {  	ve.clear(); 	double last = BE; ve.push_back(last);  	for (int i = 2; i <= 5; i++) 	{ 		double ret = last + ans;  		if (dcmp(ret - EN[i])>0)  return false;  		if (dcmp(ret - BE[i]) <= 0)  last = BE[i]; 		else  last = ret;  		ve.push_back(last);  	}  	return true;   }   double solve() {  	double le = 0, ri = EN - BE;  	while (le + eps<ri) 	{ 		double mid = (le + ri) / 2; 		if (!can(mid)) ri = mid; 		else le = mid; 	}  	double mid = (le + ri) / 2; 	can(mid); 	return mid;  } int main() {   	while (cin >> BE >> EN >> BE >> EN >> BE >> EN >> BE >> EN >> BE >> EN) 	{ 		double ans = solve();  		for (int i = 0; i<5; i++)  printf("%.2f%c", ve[i], i == 4 ? 'n' : ' ');  	}  	return 0; } ``

• 微信咨询
• 回顶