{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eAlmost every gift shop sells cubes and balls of glass with beautiful images\r\ninside them.\r\nYoung girl Anya wanted to learn the way these images are created,\r\nso she entered the department of laser technologies.\r\nNow she knows that if two laser beams of frequency 3.1415 PHz intersect\r\ninside the glass object, the glass will become opaque at the intersection\r\npoint, although this opacity will not block other laser beams passing\r\nthrough this point.\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eNow Anya herself wants to draw an image inside a polygonal prism.\r\nShe decided to start with a flat image located in a section\r\nparallel to the base of the prism.\r\nUnfortunately, Anya spilled her tea on the second laser emitter,\r\nand it broke down.\r\nHowever, Anya knows that if two laser beams will pass through some point\r\nconsecutively within a short period of time, this point will also\r\nbecome opaque.\r\nNow she wants to move the laser emitter all the way\r\nalong the perimeter of the section.\r\nLaser beam will always lie inside the plane of this section.\r\nLaser beam should always be directed to a special receiver.\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThe frequency of the laser beams is extremely high,\r\nso the opaque points will be very close to each other,\r\nand will be recognized as parts of continuous curves.\r\nAnya wants to know the total length of all these curves,\r\nand asks for your help.\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eMore formally, the section of the prism is a convex polygon with \u003ci\u003en\u003c/i\u003e vertices.\r\nInitially, Anya places an emitter at some point of its perimeter.\r\nShe then places the receiver at some other point of the perimeter\r\nsuch that the distance between the emitter and the receiver\r\nmeasured along the perimeter is \u003ci\u003ed\u003c/i\u003e.\r\nAfter that, Anya starts to move both the emitter and the receiver\r\nwith equal constant speed in one direction along the perimeter.\r\nShe stops when the emitter and the receiver move to their initial positions.\u003c/div\u003e\u003c/div\u003e\u003cimg src\u003d\"CDN_BASE_URL/f0fa45e271d097ab8cb74e74cb4ff042?v\u003d1715621503\" border\u003d\"0\" alt\u003d\"Problem illustration\" align\u003d\"RIGHT\" class\u003d\"problem_raimage\"\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThe formal definition of the resulting opaque parts of curves is as follows.\r\nConsider some moment \u003ci\u003et\u003c/i\u003e when the emitter is at point \u003ci\u003eA\u003c/i\u003e and receiver\r\nis at point \u003ci\u003eB\u003c/i\u003e.\r\nIn a near moment \u003ci\u003et\u003c/i\u003e + \u003ci\u003eε\u003c/i\u003e, the emitter\r\n(moving along the perimeter) arrives at some point \u003ci\u003eA\u003c/i\u003e\u0027 while the receiver\r\n(moving with the same speed along some other part of the perimeter)\r\narrives at some point \u003ci\u003eB\u003c/i\u003e\u0027.\r\nIn general case, there will be exactly one\r\nintersection point of segments \u003ci\u003eA\u003c/i\u003e\u003ci\u003eB\u003c/i\u003e and \u003ci\u003eA\u003c/i\u003e\u0027\u003ci\u003eB\u003c/i\u003e\u0027.\r\nNow let \u003ci\u003eε\u003c/i\u003e → 0 to get the point which becomes opaque\r\nat the moment \u003ci\u003et\u003c/i\u003e.\r\nDo that for all possible moments \u003ci\u003et\u003c/i\u003e to get all the points\r\nwhich become opaque.\r\nThis set of points in fact can be viewed as a set of curves.\r\nYour task is to find their total length.\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eOn the illustration, the perimeter is a square, dashed lines represent\r\nthe laser beam at different moments of time, and bold points are the points\r\nwhich become opaque as the emitter and the receiver move along the perimeter.\r\nThe distance between the emitter and the receiver\r\n(measured along the perimeter) remains equal to the constant \u003ci\u003ed\u003c/i\u003e.\r\nNote that it does \u003cb\u003enot\u003c/b\u003e mean the lengths of dashed lines are equal.\r\nAs you can see, the opaque points lie on a certain curve.\u003c/div\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThe first line contains an integer \u003ci\u003en\u003c/i\u003e (3 ≤ \u003ci\u003en\u003c/i\u003e ≤ 10\u0026nbsp;000).\r\nEach of the following \u003ci\u003en\u003c/i\u003e lines contains two integers which are the\r\ncoordinates of vertices of the polygon in counter-clockwise order.\r\nThe coordinates don\u0027t exceed 10\u003csup\u003e6\u003c/sup\u003e by their absolute values.\r\nIt is guaranteed that no three vertices lie on the same line.\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThe last line contains a positive integer \u003ci\u003ed\u003c/i\u003e.\r\nIt is guaranteed that \u003ci\u003ed\u003c/i\u003e doesn\u0027t exceed half of the length of polygon\u0027s\r\nperimeter and is strictly greater than the longest of its sides.\u003c/div\u003e\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eOutput the total length of all curves formed by the opaque points\r\nwith absolute or relative error not exceeding 10\u003csup\u003e−6\u003c/sup\u003e.\u003c/div\u003e\u003c/div\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n-1 0\r\n1 0\r\n0 10\r\n11\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e22.3730148246\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cbr\u003e\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4\r\n0 0\r\n10 0\r\n10 10\r\n0 10\r\n11\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e56.1255583559\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}