{"problem":{"name":"E. Ship's Shortest Path","description":{"content":"You have got a new job, and it's very interesting, you are a ship captain. Your first task is to move your ship from one point to another point, and for sure you want to move it at the minimum cost. ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF75E"},"statements":[{"statement_type":"Markdown","content":"You have got a new job, and it's very interesting, you are a ship captain. Your first task is to move your ship from one point to another point, and for sure you want to move it at the minimum cost.\n\nAnd it's well known that the shortest distance between any 2 points is the length of the line segment between these 2 points. But unfortunately there is an island in the sea, so sometimes you won't be able to move your ship in the line segment between the 2 points.\n\nYou can **only** move to safe points. A point is called safe if it's on the line segment between the start and end points, or if it's on the island's edge.\n\nBut you are too lucky, you have got some clever and strong workers and they can help you in your trip, they can help you move the ship in the sea and they will take 1 Egyptian pound for each moving unit in the sea, and they can carry the ship (yes, they are very strong) and walk on the island and they will take 2 Egyptian pounds for each moving unit in the island. The money which you will give to them will be divided between all workers, so the number of workers does not matter here.\n\nYou can move your ship on the island edge, and it will be considered moving in the sea.\n\nNow you have a sea map, and you have to decide what is the minimum cost for your trip.\n\nYour starting point is (_xStart_, _yStart_), and the end point is (_xEnd_, _yEnd_), both points will be different.\n\nThe island will be a convex polygon and there will be no more than 2 polygon points on the same line, also the starting and the end points won't be inside or on the boundary of the island. The points for the polygon will be given in the anti-clockwise order.\n\n## Input\n\nThe first line contains 4 integers, _xStart_, _yStart_, _xEnd_ and _yEnd_ ( - 100 ≤ _xStart_, _yStart_, _xEnd_, _yEnd_ ≤ 100). The second line contains an integer _n_, which is the number of points in the polygon (3 ≤ _n_ ≤ 30), followed by a line containing _n_ pairs of integers _x_ and _y_, which are the coordinates of the points ( - 100 ≤ _x_, _y_ ≤ 100), the polygon points will be distinct.\n\n## Output\n\nPrint one line which contains the minimum possible cost. The absolute or relative error in the answer should not exceed 10 - 6.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"你得到了一份新工作，非常有趣，你是一名船长。你的第一个任务是将你的船从一个点移动到另一个点，当然，你希望以最小的成本完成。\n\n众所周知，任意两点之间的最短距离是连接这两点的线段的长度。但不幸的是，海中有一个岛屿，因此有时你无法沿着两点之间的线段移动你的船。\n\n你*只能*移动到安全点。一个点被称为安全点，如果它位于起点和终点之间的线段上，或者位于岛屿的边缘上。\n\n但你太幸运了，你有一群聪明而强壮的工人，他们可以在你的旅途中帮助你：他们可以在海上帮你移动船，每移动一个单位距离收取1埃及镑；他们也可以扛着船（是的，他们非常强壮）在岛上行走，每移动一个单位距离收取2埃及镑。你支付给他们的钱将平均分给所有工人，因此工人的数量无关紧要。\n\n你可以在岛屿边缘移动你的船，这将被视为在海上移动。\n\n现在你有一张海图，必须决定你旅程的最低成本。\n\n你的起点是 (#cf_span[xStart], #cf_span[yStart])，终点是 (#cf_span[xEnd], #cf_span[yEnd])，这两个点互不相同。\n\n岛屿是一个凸多边形，且不会有超过两个多边形顶点共线，起点和终点也不会位于岛屿内部或边界上。多边形的点将按逆时针顺序给出。\n\n第一行包含4个整数：#cf_span[xStart], #cf_span[yStart], #cf_span[xEnd] 和 #cf_span[yEnd]（#cf_span[ - 100 ≤ xStart, yStart, xEnd, yEnd ≤ 100]）。第二行包含一个整数 #cf_span[n]，表示多边形的顶点数（#cf_span[3 ≤ n ≤ 30]），随后一行包含 #cf_span[n] 对整数 #cf_span[x] 和 #cf_span[y]，表示各顶点的坐标（#cf_span[ - 100 ≤ x, y ≤ 100]），所有多边形顶点互不相同。\n\n请输出一行，包含可能的最小成本。答案的绝对或相对误差不应超过 #cf_span[10 - 6]。\n\n## Input\n\n第一行包含4个整数：#cf_span[xStart], #cf_span[yStart], #cf_span[xEnd] 和 #cf_span[yEnd]（#cf_span[ - 100 ≤ xStart, yStart, xEnd, yEnd ≤ 100]）。第二行包含一个整数 #cf_span[n]，表示多边形的顶点数（#cf_span[3 ≤ n ≤ 30]），随后一行包含 #cf_span[n] 对整数 #cf_span[x] 和 #cf_span[y]，表示各顶点的坐标（#cf_span[ - 100 ≤ x, y ≤ 100]），所有多边形顶点互不相同。\n\n## Output\n\n请输出一行，包含可能的最小成本。答案的绝对或相对误差不应超过 #cf_span[10 - 6]。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ P_s = (x_s, y_s) \\in \\mathbb{R}^2 $ be the start point.  \nLet $ P_e = (x_e, y_e) \\in \\mathbb{R}^2 $ be the end point.  \nLet $ \\mathcal{I} \\subset \\mathbb{R}^2 $ be a convex polygon (the island), defined by $ n \\geq 3 $ vertices $ V_0, V_1, \\dots, V_{n-1} $, given in counter-clockwise order, with $ V_i = (x_i, y_i) $.  \nLet $ \\partial \\mathcal{I} $ denote the boundary (edge) of $ \\mathcal{I} $.  \n\nLet $ L = \\overline{P_s P_e} $ be the line segment from $ P_s $ to $ P_e $.  \n\nA *safe point* is any point in $ L \\cup \\partial \\mathcal{I} $.  \n\n**Cost Model**  \n- Movement along $ L \\setminus \\mathcal{I} $ (sea): cost = 1 per unit length.  \n- Movement along $ \\partial \\mathcal{I} $ (island edge): cost = 1 per unit length (treated as sea).  \n- Movement *inside* $ \\mathcal{I} $ (island interior): cost = 2 per unit length.  \n\n**Constraints**  \n1. $ P_s \\notin \\mathcal{I} \\cup \\partial \\mathcal{I} $, $ P_e \\notin \\mathcal{I} \\cup \\partial \\mathcal{I} $.  \n2. $ \\mathcal{I} $ is convex and simple.  \n3. No three polygon vertices are collinear.  \n\n**Objective**  \nFind the minimum cost path from $ P_s $ to $ P_e $, constrained to move only through safe points (i.e., $ L \\cup \\partial \\mathcal{I} $), where:  \n- Any segment of the path lying on $ L $ contributes cost = length.  \n- Any segment of the path lying on $ \\partial \\mathcal{I} $ contributes cost = length.  \n- The path may switch between $ L $ and $ \\partial \\mathcal{I} $ at tangent or intersection points.  \n\n**Note**: Since movement on $ \\partial \\mathcal{I} $ is charged at sea rate (1), and the path is restricted to $ L \\cup \\partial \\mathcal{I} $, the problem reduces to finding the shortest path from $ P_s $ to $ P_e $ along the union of the line segment $ L $ and the polygon boundary $ \\partial \\mathcal{I} $, with edge weights equal to Euclidean lengths.  \n\nThus, the optimal path is the shortest path in the metric space $ L \\cup \\partial \\mathcal{I} $, with distance measured by Euclidean length.  \n\n**Formal Objective**  \nCompute:  \n$$\n\\min_{\\gamma \\in \\Gamma} \\ell(\\gamma)\n$$  \nwhere  \n- $ \\Gamma $ is the set of all piecewise-linear paths from $ P_s $ to $ P_e $ such that $ \\gamma(t) \\in L \\cup \\partial \\mathcal{I} $ for all $ t $,  \n- $ \\ell(\\gamma) $ is the Euclidean length of $ \\gamma $.  \n\n*(The path may consist of: $ P_s \\to A \\to B \\to P_e $, where $ A, B \\in \\partial \\mathcal{I} $, and $ A, B $ are points of tangency or intersection with $ L $, or the direct segment $ P_s \\to P_e $ if unobstructed.)*","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF75E","tags":["geometry","shortest paths"],"sample_group":[["1 7 6 7\n4\n4 2 4 12 3 12 3 2","6.000000000"],["\\-1 0 2 0\n4\n0 0 1 0 1 1 0 1","3.000000000"]],"created_at":"2026-03-03 11:00:39"}}