Minimum Possible Path Length - Barclays Online Assessment NIT Bhopal

Problem Preview

"Gregor is a salesperson employed in the city of Cartesia, which lies on an infinite plane. The locations of retailers follow the Cartesian coordinate system. There are **N + 1** retailers in the city: * **N retailers**, with positions **1 to N**, have coordinates: [ (X_1, 0), (X_2, 0), \ldots, (X_N, 0) ] i.e., all these retailers lie on the **X-axis**. * The **head retailer**, with position **N + 1**, is located at: [ (X_{N+1}, Y_{N+1}) ] Gregor wants to find the **shortest possible path** starting from the **K-th retailer** and visiting **all the other retailers exactly once**. He may visit the head retailer **twice** during the route. The distance between two retailers is the Euclidean distance between their corresponding Cartesian coordinates. Print the minimum possible path length, rounded to **6 decimal places**. --- ## Function Description ```cpp double minPossLen( int posK, vector<int> retailerXCoord, int headXCoord, int headYCoord ); ``` ### Parameters * **posK** – Position (1-indexed) of the starting retailer. * **retailerXCoord** – List containing the X-coordinates of the N retailers on the X-axis. * **headXCoord** – X-coordinate of the head retailer. * **headYCoord** – Y-coordinate of the head retailer. --- ## Input Format 1. Integer **posK** – starting retailer position. 2. Integer **num** – number of retailers on the X-axis. 3. **num** space-separated integers – X-coordinates of the retailers. 4. Integer **headXCoord**. 5. Integer **headYCoord**. --- ## Output Format Print a single floating-point number representing the **minimum possible path length**, rounded to **6 decimal places**. --- ## Constraints * (1 \le \text{posK} \le \text{num} + 1) --- ## Example ### Input ```text 1 3 0 1 2 1 1 ``` ### Output ```text 3.828427 ``` ### Explanation * Retailers are located at: * (0, 0) * (1, 0) * (2, 0) * Head retailer is at: * (1, 1) * Starting retailer: * (0, 0) One minimum path is: ```text (0,0) → (1,1) → (0,0) → (1,0) → (2,0) ``` Path length: ```text √2 + √2 + 1 + 1 = 1.4142135 + 1.4142135 + 1 + 1 = 3.828427 ``` Hence, the minimum possible path length is: ```text 3.828427 ```"