ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Ural SU and Orel STU contest. Petrozavodsk training camp. Summer 2006

About     Problems     Submit solution     Judge status     Standings
Contest is over

B. No Smoking!

Time limit: 1.5 second
Memory limit: 64 MB
Vasya is a good boy, but he has a bad habit: he smokes. All the time that Petya is Vasya's friend, he's been trying to cure Vasya of this habit. But he never succeeded, because Vasya doesn't want to leave off smoking.
Recently Petya invented a new way to cure his friend. Vasya is a sloven, so his cigarettes are not in a pack but lie scattered on a big table. Petya wants to take away one cigarette every day so that Vasya wouldn't notice it. Petya wants to take away a cigarette that intersect other cigarettes on the table. Help Petya to determine if he can start to implement his plan.


A cigarette is a segment with non-zero length. The first line contains the number of cigarettes on Vasya's table N (1 ≤ N ≤ 50000). The next N lines describe the cigarettes: in the (i + 1)st line there are integers x1, y1, x2, y2, which are the coordinates of the ends of the ith cigarette (–10000 ≤ x1, y1, x2, y2 ≤ 10000).


If Petya can start to implement his plan, then in the first line you should output the word “YES”, and the second line should contain numbers i and j, where i is the number of the cigarette that must be taken away, and j is the number of the intersecting cigarette.
If Petya can take away no cigarettes, then output “NO”.


0 0 2 2
0 2 2 0
1 2
0 0 0 5
5 0 5 10
Problem Author: Ilya Shishkov
Problem Source: Ural SU and Orel STU Contest. Petrozavodsk Summer Session, August 2006
To submit the solution for this problem go to the Problem set: 1469. No Smoking!