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

Open Ural SU Championship 2009

About     Problems     Submit solution     Judge status     Standings
Contest is over

B. Forgotten Technology

Time limit: 1.0 second
Memory limit: 64 MB
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.


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 the length of the shortest path to the disc, accurate to at least 10–5. It is guaranteed that the required path exists.


-4 -3 8 6 5 10 -7 1
1 7 5
7 -1
Problem Author: Pavel Atnashev (idea by Alex Samsonov)
Problem Source: XIV Open USU Championship
To submit the solution for this problem go to the Problem set: 1733. Forgotten Technology