Preparing NOJ

Given *n* segments in the two dimensional space, write a program, which determines if there exists a line such that after projecting these segments on it, all projected segments have at least one point in common.

Input begins with a number *T* showing the number of test cases and then, *T* test cases follow. Each test case begins with a line containing a positive integer *n* ≤ 100 showing the number of segments. After that, *n* lines containing four real numbers *x*_{1} *y*_{1} *x*_{2} *y*_{2} follow, in which (*x*_{1}, *y*_{1}) and (*x*_{2}, *y*_{2}) are the coordinates of the two endpoints for one of the segments.

For each test case, your program must output "Yes!", if a line with desired property exists and must output "No!" otherwise. You must assume that two floating point numbers *a* and *b* are equal if |*a* - *b*| < 10^{-8}.

3 2 1.0 2.0 3.0 4.0 4.0 5.0 6.0 7.0 3 0.0 0.0 0.0 1.0 0.0 1.0 0.0 2.0 1.0 1.0 2.0 1.0 3 0.0 0.0 0.0 1.0 0.0 2.0 0.0 3.0 1.0 1.0 2.0 1.0

Yes! Yes! No!

Info

Provider POJ

Origin Amirkabir University of Technology Local Contest 2006

Code POJ3304

Tags

Submitted 92

Passed 46

AC Rate 50%

Date 03/06/2019 16:12:27

Related