3 人解决，6 人已尝试。
4 份提交通过，共有 57 份提交。
8.8 EMB 奖励。
3381. Endless Turning
单点时限: 1.0 sec
内存限制: 256 MB
Last week your little sister celebrated her birthday, and she was very pleased with her birthday present: a brand new scooter! Since then several times a day she goes for a drive, without telling anyone. She will leave the house, and go right on the pavement along the road. Fortunately she knows that she is not allowed to cross the road, and she is not sufficiently skilful with her new toy to turn around on the pavement. This means that, in order to continue her way, at each intersection she must turn right.
Every time your sister sets out, you are sent after her, of which you grow tired. Thus, knowing your little sister’s ways with her scooter, you decide to write a program to find her.
The city consists of $R$ roads. Each road has a name which does not contain any spaces, and is an infinite line in the Euclidean plane. No three roads go through one point, i.e. at every intersection exactly two roads intersect. You figured out that your sister by this time should have completed $N$ turns on the intersections of the city, unless of course she managed to leave the city by travelling on a road in a direction in which there is no other intersection, in which case she might not be able to even complete $N$ turns. Your task is to write a program that tells you on which road your sister is right now.
输入格式
The first line contains four integers: the number of roads $R$, the number of turns $N$ and the $X$- and $Y$-coordinate of your parents’ home, satisfying $1 \leq R \leq 100$, $0 \leq N \leq 10^{10}$ and $|X|, |Y| \leq 10^7$.
The next $R$ lines each describe a street. Each line contains one string $S$ (without spaces, containing only alphanumeric characters, of length at most $20$), the name of the street, and four integers $X_1$, $Y_1$, $X_2$, and $Y_2$, satisfying $|X_1|, |X_2|, |Y_1|, |Y_2| \leq 10^7$ and $(X_1, Y_1) \neq (X_2, Y_2)$, indicating that road S goes through points $(X_1, Y_1)$ and $(X_2, Y_2)$.
The location of your parents’ home $(X, Y)$ is guaranteed to lie on a unique non-vertical street (i.e. not on an intersection), on the south (negative $Y$ -direction) side of the street, meaning that your little sister will depart in the east (positive $X$) direction. Moreover, each intersection is guaranteed to have coordinates of absolute value at most $10^7$, and is guaranteed to lie at least $10^{−4}$ from each other intersection in the same street.
输出格式
Output a single line containing the name of the road where your little sister can be found.
样例
Input
3 4 1 1 Broadway 0 0 0 1 Narrowlane 0 0 1 0 Homedrive 1 1 2 0
Output
Narrowlane
Input
3 4 1 0 Broadway 0 0 0 1 Narrowlane 0 0 1 0 Homedrive 1 1 2 0
Output
Homedrive
提示
In the first case your sister starts on Homedrive heading east, turns right on Narrowlane, Broadway, Homedrive and Narrowlane, which means that after four turns she is in Narrowlane.
In the second case your sister starts on Narrowlane heading east and turns right on Homedrive, leaving the city behind her. She will never finish four turns and ends on Homedrive.
创建: 7 年，1 月前.
修改: 7 年，1 月前.
最后提交: 3 年，12 月前.
题目标签