CEOI09TR - Tri
You are given K points with positive integer coordinates. You are also given M triangles, each of them having one vertex in the origin and the other 2 vertices with non-negative integer coordinates.
You are asked to determine for each triangle whether it has at least one of the K given points inside. (None of the K points are on any edge of any triangle.)
Input
The first line of the input file will contain K and M. The following K lines will contain 2 positive integers x y separated by one space that represent the coordinates of each point. The next M lines have 4 non-negative integers separated by one space, (x1, y1) and (x2, y2), that represent the other 2 vertices of each triangle, except the origin.
Output
The output file should contain exactly M lines. The k-th line should contain the character Y if the k-th triangle (in the order of the input file) contains at least one point inside it, or N otherwise.
Constraints
- 1 ≤ K, M ≤ 100 000
- 1 ≤ each coordinate of the K points ≤ 109
- 0 ≤ each coordinate of the triangle vertices ≤ 109
- Triangles are not degenerate (they all have non-zero area).
- In 50% of the test cases, all triangles have vertices with coordinates x1 = 0 and y2 = 0. That is, one edge of the triangle is on the x-axis, and another is on the y-axis.
- if (0, 0), (x1, y1) and (x2, y2) are 3 vertices of the query triangle and x1 < x2, then y1 > y2.
Example
Input 1: 4 3 1 2 1 3 5 1 5 3 1 4 3 3 2 2 4 1 4 4 6 3 Output 1: Y N Y
Input 2: 4 2 1 2 1 3 5 1 4 3 0 2 1 0 0 3 5 0 Output 2: N Y
Explanation for Example 1
Explanation for Example 2
hide comments
[Rampage] Blue.Mary:
2022-12-02 09:48:04
@Simes
|
|
Mihael:
2015-08-27 22:47:21
I found a test case for which my first AC submission gives the wrong output:
|
|
Bartek Dudek:
2012-06-03 11:39:09
Nice problem :) |
Added by: | Andrés Mejía-Posada |
Date: | 2010-01-18 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: NODEJS OBJC PERL6 SQLITE VB.NET |
Resource: | CEOI 2009 - Tîrgu Mureş, Romania |