Problem F. Function with constraints ≡

Statement

Let's consider a function of the following form: F(X, Y) = AB ⋅ X + CD ⋅ Y.

The task is to find integer values for A, B, C and D, such that for a given set of points (X_i, Y_i)
the specified function satisfies pre-determined conditions:
RoundDawn(F(X_i, Y_i)) = Z_i or RoundUp(F(X_i, Y_i)) = Z_i,
where RoundDawn() и RoundUp() — denote rounding down and rounding up, respectively.

Input format

The input begins with the number N, followed by N conditions, each written in the following format.

First, the operation sign is indicated: '>' for RoundDawn or '<' for RoundUp.

Then, three integers follow: X_i, Y_i, Z_i.

Output format

If the problem has a solution, the output contains the number 1,
followed by the found values of A, B, C and D.

If there is more than one solution, any of them can be output.

If there is no solution, the output is the single number 0.

Constraints

All input values are integers.

 − 40 ≤ (X_i, Y_i, Z_i) ≤ 40, 0 < N ≤ 2000

Sample tests

4

> -2 -5 -6
<  3  7  8
> -1  1  1
<  4 -3 -5

1
-16 37
93 74

4

> -3 -1  1
<  5 -3 -6
>  7  4  1
<  2 -1 -3

0

Explanation

Несложно заметить, что исходная задача может быть сведена к решению системы линейных неравенств:

Z_i + 1 > α  ⋅ X_i + β  ⋅ Y_i ≥ Z_i — для условий типа RoundDawn;

Z_i − 1 < α  ⋅ X_i + β  ⋅ Y_i ≤ Z_i — для условий типа RoundUp.

Для ее решения можно воспользоваться методом исключения Фурье-Моцкина.

В каждом из исходных неравенств сгруппируем слагаемые так, чтобы их можно было записать одним из указанных способов:
α  > L_i(β) или α  < U_j(β), где L_i(β) и U_j(β) представляют собой линейные функции, зависящие только от β.

Здесь и далее для простоты записи будем использовать знаки только строгих неравенств.

Будем считать, что всего у нас получилось n неравенств 1-го типа и m неравенств 2-го типа.

Попарно сгруппируем неравенства 1-го и 2-го типов, получив набор из n × m неравенств:
L_i(β) < α  < U_j(β).

Из указанных неравенств легко исключить переменную α, приведя их к следующему виду:
L_i(β) < U_j(β).

Далее, выполнив группировку подобных слагаемых, приведем их к одному из двух видов:
β  > P_l, β  < Q_k.

Здесь P_l и Q_k являются константами, независящими от β.

Таким образом, получим набор тривиальных неравенств относительно β, для которой определим допустимый интервал,
путем пересечения интервалов, определенных каждым из входящих в него неравенств.

Если результатом является пустое множество, значит система несовместна, и решений нет.

В противном случае выберем любое решение на таком интервале, и обозначим его β^*.

Подставив β^* в исходную систему, получим набор тривиальных неравенств для α.

Решая их аналогичным способом, найдем значение α^*.

Из условия задачи нас интересуют только те решения, которые могут быть выражены в виде рациональной дроби.

По этой причине, во всех операциях будем использовать рациональную арифметику.

Обратим внимание, что в исходной системе
встречаются как строгие, так и нестрогие неравенства.

Это следует учитывать при формировании
итогового интервала и выборе на нем решения.

Сложность алгоритма для системы
с двумя неизвестными O(N²).