Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: Geometry with a ruler
Description 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 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 Input file contains number of points y. Next comes number of construction operations _{N}M followed by M quads of integers a _{i}b _{i}c _{i}d, where _{i}k-th quad means that a new point is constructed as an intersection of lines containing pairs of points a, _{i}b and _{i}c, _{i}d. Such a point is guaranteed to exist. Constructed point is assigned a number_{i} N + k and can be used in following operations.## Constraints4 ≤ y ≤ 10_{i}^{6} Output 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. Sample Input
Sample Output
Hint Bold texts appearing in the sample sections are informative and do not form part of the actual data. Source Northeastern Europe 2006, Far-Eastern Subregion |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator