Winter. End of December. Snowing. The shrill wind catches snowflakes
and carries them among the stone buildings. The monastery looks
deserted—doors are blocked by snow drifts, shutters are closed.
Only the windows of the scriptorium—the largest ones in the monastery—are
wide open. Dim winter light illuminates the room. A few monks
sit there in complete silence. The room is so cold that monks' fingers
go numb and white, but they continue to quickly write with quill pens,
trying to do as much as possible during the short December day.
A sacred rite is being performed in the scriptorium—information
is being copied.
One scribe, not long ago promoted from an apprentice, is writing
his first book. His lips are moving, he mumbles every word he's
copying to ensure against mistakes. Another one has copied dozens
of books, every letter he writes is indistinguishable
from the original. He devoted all his life to writing,
and he has no other skills.
A monk, called corrector, is sitting in the adjacent room.
His duty is no less important—he's leaving notes and
corrections in the margins of a book. Also, binders and
illuminators are working in the scriptorium. They add
final touches to a book before it ends up in rich layman's
hands. Hard work of all these monks is essential for survival
of the monastery.
But daylight fades, scribes put quills aside and go away
to their cells. The day is drawing to a close. The year 1439
is drawing to a close. The epoch of monk scribes is drawing to a close.
Next year, 1440, Johannes Gutenberg will print his first book.
Autumn. Mid-November. Raining. Young woman is sitting at the diner
on the corner of Broadway and 112th Street. She looks out the window
at the dark clouds hanging over the city. Maybe it's just the weather,
but all the morning she feels strange emptiness in her soul. She
feels like apathetic observer, like nothing concerns her.
The waiter comes to her and fills her cup with coffee halfway.
She tries to argue, but he doesn't look at her anymore. He's
looking at a woman entering the diner and shaking her umbrella.
He smiles and greets her. Young woman turns her head away from
them and pours milk in her coffee.
Feeling bored, she picks the newspaper. Nothing interesting in it,
except a story about an actor who drank too much, slipped in his
apartment and died. However, his name doesn't sound familiar to her.
She turns the pages looking for the horoscope and comic strips.
She thinks someone is watching her. She turns her head and sees a woman
behind the window, looking inside. In a moment, she realizes that the woman is
just looking at her reflection, fixing her stockings.
And the rain goes on and on. She hears the bells of the Cathedral
of Saint John the Divine, located opposite the end of the street.
The bells ringing remind her of an old friend, with whom she once
had a little picnic on the steps of the cathedral at midnight.
She finishes her coffee and leaves the diner. The diner's name
is “Tom's”. Young woman's name is Suzanne Vega. In a few
months she'll write a song about this morning. And in a decade
audio engineer from Germany will use the song to fine-tune
his compression algorithm. He'll listen to it thousands of times,
before final version of the compression scheme known as MP3
will be ready.
In the Museum of Science History, in the “Forgotten Technology”
section, there is an exhibit called “Mass Copy Victims”.
Under the glass, a 15th century hand-written book lies on the velvet
cloth. A 20th century compact disk lies on top of the book.
These technologies have been forgotten with the advent of new ways
to copy and distribute information. Hand-written books lost competition
with cheap output of printing presses, while compact disks were forced
out by pervasive digital networks. And now you can find them only
in private collections and this museum.
Also, a little mouse lives in the museum. She lives there because
she's curious and adores museums. She gnawed through the bottom of
the showcase, and now she wants to bite a bit of the disk and
take it away to her hole. But she's afraid that the alarm will
set off before she makes it. Help her to find the shortest path
to the disk.
The book is a rectangle. The disk is lying on the book,
so its center is either inside the rectangle or on its border.
The mouse can run only on the cloth, her own dimensions are negligible.
In her initial position, there is a non-zero distance between her
and the book/the disk. To bite the disk, the mouse has to run to
a point where the disk hangs over her, that is the point should
be strictly outside the rectangle.
Input
The first line contains the coordinates of the vertices of the rectangle,
listed in the counter-clockwise order. The next line contains the coordinates
of the center of the disc and its radius. The third line contains the coordinates
of the initial position of the mouse. All numbers are integers and don't exceed 1000
in absolute value. The radius of the disc is equal or greater than 1.
Output
Output the length of the shortest path to the disc, accurate to at least 10–5. It is guaranteed
that the required path exists.
Sample
input | output |
---|
-4 -3 8 6 5 10 -7 1
1 7 5
7 -1
| 12.07107
|
Problem Author: Pavel Atnashev (idea by Alex Samsonov)
Problem Source: XIV Open USU Championship