Geometry with a ruler
Ограничения: время – 3s/6s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Classic geometric construction is based on two instruments: ruler and compass. However, some
constructions are possible using only the ruler. Specifically, let us define that if we have a set
of `N` points, we can select two pairs of them, draw a line through each pair, and construct a
new point as an intersection of these two lines. New point can then be added to the set as `(N\ +\ 1)`-th
point, and the process repeated.
Such geometric constructions are abstract notions, and attempt to verify
them with physical pencil and ruler can lead to errors caused by imprecision of these instruments.
So you are tasked to write a program that does exact verification.
Your program must read a set of points and a sequence
of constructing operations and find out whether the point with coordinates `(0,\ 0)` is one of
the constructed points. Note that, similar to physical instruments, floating point
calculations performed by computers are also imprecise. This should not, of course, alter verification
results.
Input file format
Input file contains number of points `N` followed by their integer coordinates `x_1\ y_1\ x_2\ y_2\ …\ x_N\ y_N`. Next
comes number of construction operations `M` followed by `M` quads of integers `a_i\ b_i\ c_i\ d_i`,
where `k`-th quad means that a new point is constructed as an intersection of
lines containing pairs of points `a_i`, `b_i` and `c_i`, `d_i`. Such a point is guaranteed to exist.
Constructed point is assigned a number `N\ +\ k` and can be used in following operations.
Output file format
Output file must contain a single integer – number of the first
operation which constructs a point `(0,\ 0)`, or 0 (zero), if there is no such operation.
Constraints
`4\ ≤\ N\ ≤\ 100`, `1\ ≤\ M\ ≤\ 10`, `-10^6\ ≤\ x_i,\ y_i\ ≤\ 10^6`
Sample Input 1
4
-1 -1 -2 2 2 2 1 -1
1
1 3 2 4
Sample Input 2
4
-1000 -1000 -2000 2000 2001 2000 1000 -1000
1
1 3 2 4
Source: NEERC ICPC, Far Eastern subregion, 2006