Problem C
Fortnite Quests
As a budding Fortnite1 enthusiast, you know that the quickest way to level up is by completing quests. A quest is a task that must be completed in a specific location. You are focused on completing a sequence of quests, where each quest is a prerequisite to complete the next: that is, in order to complete a later quest, you must complete all earlier quests.
Your goal is to finish the full sequence of quests in as little time as possible. The time it takes to get from one quest to another is the square of the Euclidean distance between the coordinates of the two quests. Once you arrive at the coordinate location for a particular quest, the quest is completed instantly.
Note that the Euclidean distance between the points $(X_1, Y_1)$ and $(X_2, Y_2)$ would be calculated as
\[ \sqrt{(X_2 - X_1)^2 + (Y_2 - Y_1)^2} \]Lastly, as a new Fortnite player, you are given an amount $V$ of in-game currency called V-bucks. $1$ V-buck can be spent to instantly complete the current quest, regardless of where you are on the map, essentially skipping that quest. In theory, given enough V-bucks, every quest can be completed in this way; however, the first and final quests are unskippable, and therefore must be completed at their listed locations. You may assume that you begin at the location of the first quest (and thus may complete it instantly).
Given the order and location of each quest, as well as the amount $V$ of in-game currency you can spend to complete quests, determine the minimum amount of time it will take to complete the full sequence of quests.
Input
The first line will consist of two space-separated integers: $N$ ($2 \leq N \leq 100$), the number of quests, and $V$ ($0 \leq V \leq N-2$), the amount of V-bucks you have to spend.
The following $N$ lines will each consist of two space-separated integers $X$ and $Y$ ($-10\, 000 \leq X, Y \leq 10\, 000$). All pairs of points are distinct; that is, no two quests appear at the same location.
Output
Output a single integer, the minimum amount of time required to complete all $N$ quests. Since the answer can be quite large, print the answer modulo $10^{9}+7$.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 0 0 0 1 0 0 1 |
3 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 1 0 0 1 0 0 1 |
1 |
| Sample Input 3 | Sample Output 3 |
|---|---|
7 3 10 10 -2 7 0 -3 9 9 8 8 -100 -100 7 7 |
6 |
Footnotes
- Fortnite © Epic Games, Inc. Used here for educational purposes only, in accordance with fair use as defined by section 107 of the Copyright Act.