Wowo is a solo adventurer who completed many dangerous journeys on his own foot in forests, deserts and even glaciers. The Shanghai ICPC committee invited Wowo as a tester of their new running trial.The trial can be described as a 2D simple polyline. ). The line segments do not intersect with each other except that two consecutive line segments. . Any two consecutive segments have different directions. The committee wants Wowo to run from. However, Wowo has a smart device that can hack the committee's system for an interval of time. Wowo is able to choose 2 points
Wowo is a solo adventurer who completed many dangerous journeys on his own foot in forests, deserts and even glaciers. The Shanghai ICPC (Shanghai Invitational Contest on Programmable Cheating) committee invited Wowo as a tester of their new running trial.
The trial can be described as a 2D simple polyline
(p_1,ldots, p_n)
(p
1
,…,p
n
). In other words, the trial consists of
{n-1}
n−1 line segments
(p_1, p_2),ldots, (p_{n-1}, p_n)
(p
1
,p
2
),…,(p
n−1
,p
n
). The line segments do not intersect with each other except that two consecutive line segments
(p_i, p_{i+1})
(p
i
,p
i+1
) and
(p_{i+1}, p_{i+2})
(p
i+1
,p
i+2
) intersect at the point
p_{i+1}
p
i+1
. Any two consecutive segments have different directions. The committee wants Wowo to run from
p_1
p
1
to
p_n
p
n
along the line segments
(p_1,p_2),ldots, (p_{n-1}, p_n)
(p
1
,p
2
),…,(p
n−1
,p
n
) in order.
However, Wowo has a smart device that can hack the committee's system for an interval of time. Wowo is able to choose 2 points
{a, b}
a,b on the trial and run directly from
{a}
a to
{b}
b along the line segment
{(a, b)}
(a,b). Each of these
{a}
a and
{b}
b can be some
p_i
p
i
(
1le ile n
1≤i≤n) and can be some point on some line segment
(p_i, p_{i+1})
(p
i
,p
i+1
) (
1le i
标签： HBC214890蓝廋
香菇
枚举Wowoear题解
