Задачки

[LisandreL]

Понятно как выявить тройку за 7 забегов:
Вначале все лошади участвуют в заездах по 1 разу. Того 5 заездов.
Далее победителей (первые места) сводим в 1 заезде. Обозначим их как a1, b1, c1, d1, e1 в порядке прихода к финишу. Бегавших с ними в подготовительных раундах обозначим той же буквой, но цифрой соответствующей месту.

a1 b1 c1 d1 e1
a2 b2 c2 d2 e2
a3 b3 c3 d3 e3
a4 b4 c4 d4 e4
a5 b5 c5 d5 e5

Тогда на место в тройке могут претендовать выделенные лошади. У остальных заведомо есть 3+ лошади быстрее их ( например для b3 быстрее её b2 и b1, так как они участвовали в 1 забеге и a1, так как она быстрее b1).
Остаётся 6 лошадей, но a1 гарантированно самая быстрая. Тогда среди оставшихся 5 проводим забег и 2 его победителя и займут 2-ое и 3-ье место в рейтинге лошадей.

Осталось доказать, что менее чем за 7 заездов этого выяснить нельзя.

Соображение 1: если лошадь не принимала участие ни в одном забеге, то про неё ничего сказать нельзя, значит каждая лошадь должна участвовать хотя бы в 1 забеге.
Итого получаем минимум 5 забегов.

Соображение 2: если забегов ровно 5 и каждая лошадь участвовала, то они участвовали ровно один раз и выявить тройку ещё нельзя ( у нас получается 9 претендентов).

Вот. Осталось разобраться с 6 забегами.

P.S. Разумеется решаем, в предположении, что лошади всегда бегают одинаково.

[Igors]

Да, с предъявленной матрицей все сразу становится ясно. Кстати это похоже как пакует jpg (когда-то (давно) изучал)

[m_ax]

LisandreL Да, совершенно верно)

[brankovic]

LisandreL Да, совершенно верно)

А почему за 6 нельзя? В смысле как это доказать?

[m_ax]

LisandreL Да, совершенно верно)

А почему за 6 нельзя? В смысле как это доказать?

Как доказать не знаю) Не думал об этом.
Видимо, нужно рассуждать так, что после пяти забегов (а это однозначно пять по пять лошадей) минимальное число лошадей в которое входят три самых быстрых, больше пяти.  

[Igors]

Есть QPolygonF с числом точек >= 3. Определить порядок следования точек (по или против часовой стрелки)

[m_ax]

Есть QPolygonF с числом точек >= 3. Определить порядок следования точек (по или против часовой стрелки)

Если контур без самопересечений, то берёте любую точку (A0) и строите вектор M следующим образом:
Разбиваете ваш контур на вектора ai и берёте сумму всех векторных произведений каждого вектора с вектором проведённого из т. A0 к началу каждого вектора ai. Получившийся таким образом вектор M будет иметь только z компоненту и если она > 0 то движение происходит по часовой стрелки, в противном случае - против часовой.
Вроде так))
   

[kambala]

иногда в качестве A0 используют центр полигона

определение порядка следования часто используется при построении выпуклой оболочки (алгоритм Грэхема например)

[Igors]

Если контур без самопересечений, то берёте любую точку (A0) и строите вектор M следующим образом:
Разбиваете ваш контур на вектора ai и берёте сумму всех векторных произведений каждого вектора с вектором проведённого из т. A0 к началу каждого вектора ai. Получившийся таким образом вектор M будет иметь только z компоненту и если она > 0 то движение происходит по часовой стрелки, в противном случае - против часовой.
Вроде так))

То есть Вы считаете что такое объяснение вполне понятно широкому кругу читателей? Как там в гоблинском переводе

Я человек военный - говори два разА и медленно!

В данном случае исходник ф-ции сказал бы намного больше и лучше, прототип напр такой

Код

C++ (Qt)
int CheckPolygonClockwise( const QPolygonF & poly );
 

Так что есть возможность блеснуть техникой С++ (если таковая имеется)

[m_ax]

Если контур без самопересечений, то берёте любую точку (A0) и строите вектор M следующим образом:
Разбиваете ваш контур на вектора ai и берёте сумму всех векторных произведений каждого вектора с вектором проведённого из т. A0 к началу каждого вектора ai. Получившийся таким образом вектор M будет иметь только z компоненту и если она > 0 то движение происходит по часовой стрелки, в противном случае - против часовой.
Вроде так))

То есть Вы считаете что такое объяснение вполне понятно широкому кругу читателей? Как там в гоблинском переводе

Я человек военный - говори два разА и медленно!

В данном случае исходник ф-ции сказал бы намного больше и лучше, прототип напр такой

Код

C++ (Qt)
int CheckPolygonClockwise( const QPolygonF & poly );
 

Так что есть возможность блеснуть техникой С++ (если таковая имеется)

Как то так:

Код

C++ (Qt)
int CheckPolygonClockwise( const QPolygonF & poly )
{
    double M_z = 0.0;
    int size = poly.size();
    QPointF a = poly[size-1];
    QPointF b = poly[0]-poly[size-1]; 
    M_z += (a.x() * b.y() - a.y() * b.x());
    for (int i = 0; i < size-1; ++i) {
        a = poly[i];
        b = poly[i+1]-poly[i]; 
        M_z += (a.x() * b.y() - a.y() * b.x());
    }
    return (M_z > 0.0) ? 1 : -1;
}
 

Код написан на коленках, так что дорабатывайте сами))

Если интересно, могу показать откуда всё это следует.

[ufna]

[irony]
m_ax, с вероятностью 99% ты допустил ошибку, которая говорит, что ты ничего не понимаешь в этой области, или просто даже не понял задачу!
[/irony]

[m_ax]

[irony]
m_ax, с вероятностью 99% ты допустил ошибку, которая говорит, что ты ничего не понимаешь в этой области, или просто даже не понял задачу!
[/irony]

ufna, я уже морально готов к ентому))

Кстати, реально нашёл ошибку, там (4 строчка) вместо

Код

C++ (Qt)
QPointF b = poly[size-1]-poly[0]; 
 

нужно

Код

C++ (Qt)
QPointF b = poly[0]-poly[size-1]; 
 

Подправил))

[Igors]

Все Вы правильно сказали, но объяснили (мягко говоря) неважно. Векторное произведение принимает 2 вектора и возвращает вектор который перпендикулярен обоим входным. Есть важное свойство: длина возвращаемого вектора равна (удвоенной) площади треугольника образованного 2-мя входными. Поэтому площадь треугольника равна половине длины векторного произведения любых его 2-х сторон.

Рассмотрим треугольник ABC и точку O.

S(ABC) = S(OAB) + S(OBC) + S(OCA);  // S - площадь

Когда O внутри ABC - все очевидно. Но даже если O снаружи - результат тот же. На плоскости XY площадь есть Z выходного вектора и знак Z (плюс или минус) как раз и определяется направлением обхода. Два слагаемых получатся с одним знаком а третье с другим, в итоге все равно знаковая площадь ABC.

Код

C++ (Qt)
// возвращает знаковую удвоенную площадь треугольника (O(0, 0), p0, p1)
inline qreal Square( const QPointF & p0, const QPointF & p1 ) 
{
 return p0.x * p1.y - p0.y * p1.x;
}
 
// возвращает знаковую удвоенную площадь полигона
// нужна для выяснения направления обхода но может пригодиться и сама по себе
qreal PolySquare( const QPolygonF & poly )
{
 qreal sum = 0.0f;
 int i, limit = poly.size();
 for (i = 0; i < limit; ++i)
  sum += Square(poly[i], poly[(i + 1) % limit]);
 return sum;
}
 
// зная знак площади, возвращаем направление обхода
enum {
  POLY_ORDER_UNDEF = -1,   // площадь полигона слишком мала (вырожденный)
  POLY_ORDER_CW = 0,        // по часовой 
  POLY_ORDER_СCW = 1,      // против часовой 
};
const qreal POLY_FUDGE = 1.0e-5f;  // предел точности 
 
int PolyClockwise( qreal polySquare )
{
 if (fabs(polySquare) < POLY_FUDGE) return POLY_ORDER_UNDEF;
 return (polySquare > 0.0) ? POLY_ORDER_СCW : POLY_ORDER_CW;
}
 

Писал тоже прямо здесь (все по-честному  )  

[Lagovas]

Мы хотели бы пересечь на джипе 1000-мильную пустыню, израсходовав при этом минимум горючего. Объем топливного бака джипа 500 галлонов, горючее расходуется равномерно, по 1 галлону на милю. В точке старта имеется неограниченный резервуар с топливом. Так как в пустыне нет складов горючего, мы должны установить свои собственные хранилища и наполнить их топливом из бака машины.
Где расположить эти хранилища?
Сколько горючего нужно залить в каждое из них?
Какое наименьшее количество бензина требуется для преодоления пустыни?

[m_ax]

Мы хотели бы пересечь на джипе 1000-мильную пустыню, израсходовав при этом минимум горючего. Объем топливного бака джипа 500 галлонов, горючее расходуется равномерно, по 1 галлону на милю. В точке старта имеется неограниченный резервуар с топливом. Так как в пустыне нет складов горючего, мы должны установить свои собственные хранилища и наполнить их топливом из бака машины.
Где расположить эти хранилища?
Сколько горючего нужно залить в каждое из них?
Какое наименьшее количество бензина требуется для преодоления пустыни?

Прикольная задачка)

И так, у меня получилось следующие:
Необходимо три хранилища, расположенные на расстояниях
1) 500/3,
2) 2*500/3,
3) 500
милях.
Заполняется вначале первое хранилище объёмом в 5 баков, т.е. 5*500 = 2500 галлонов.
Первое хранилище заполнено, мы находимся в самом начале пустыни, заправляем полный бак и едем к первому хранилищу.
В итоге у нас 5 баков в первом хранилище  и оставшиеся 2/3 бака в машине.

Заполняем второе хранилище, перевозя весь бензин из первого во второе. Получается, что после этого мы нах. у второго хранилища с пустым баком в машине и двумя баками в хранилище: 2*500 = 1000 галлонов.

Далее наполняем полный бак в машину едем к третьему хранилищу и заполняем его 1/3 бака и на оставшемся бензине 1/3 бака возвращаемся ко второму хранилищу.  

Заливаем полный бак (оставшийся во втором хранилище), едем до третьего хранилища, потратив при этом 1/3 бака. Восполняем эти 1/3 бака из третьего хранилища и пересекаем оставшиеся 500 миль с полным баком.

Всего получается нужно 16 баков, т.е. 16*500 = 8000 галлонов топлива.

Как то так, но не уверен, что нет варанта более оптимального.