Найти минимальный отрезок прямой, содержащий максимум точек
Не могу решить задачу с acmp на c++. Кто может помочь? Само условие:
На прямой отмечено N точек. Требуется найти такой отрезок длины L, на котором лежат M из отмеченных точек (M ≥ 2), что величина L/M минимальна. Считается, что точки, совпадающие с одним из концов отрезка, лежат на нем.
Входные данные Входной файл INPUT.TXT содержит количество точек N (2 ≤ N ≤ 10000). На второй строке записаны координаты этих точек Xi - целые числа, разделенные пробелами. При этом |Xi| ≤ 30000 и Xi < Xj при i < j.
Выходные данные В выходной файл OUTPUT.TXT выведите координаты начала и конца найденного отрезка A и B (A < B). Если решений несколько, выведите любое.
Ответы (1 шт):
int main()
{
int N, a, b, c, d, L = 1000000;
cin >> N;
cin >> c;
for(int i = 0; i < N-1; ++i)
{
cin >> d;
if (d - c == 1)
{
cout << c << " " << d << endl;
return 0;
}
if (d - c < L)
{
L = d - c;
a = c;
b = d;
}
c = d;
}
cout << a << " " << b << endl;
}
Так как все точки различны, минимум - при расстоянии 1 (сами подумайте, что будет, если добавить еще точку.). Если находим такую пару точек, выводим ее. Если не находим - запоминаем текущий минимум длины, и идем к следующей паре...