github.com/captn3m0/codechef.git

---
{"category_name":"easy","problem_code":"NI02","problem_name":"KGP Summers","languages_supported":{"0":"C","1":"CPP 4.3.2","2":"CPP14","3":"GO","4":"JAVA"},"max_timelimit":3,"source_sizelimit":50000,"problem_author":"iitgfaculties","problem_tester":null,"date_added":"2-11-2012","tags":{"0":"iitgfaculties"},"time":{"view_start_date":1352628298,"submit_start_date":1352628298,"visible_start_date":1352627003,"end_date":1735669800},"layout":"problem"}
---
<span class="solution-visible-txt">All submissions for this problem are available.</span><p style="text-align:justify">Summers in Kharagpur are Hot. And Humid! It’s pretty rough for students who are new to KGP and are not used to the sweating it can cause.</p>
<p style="text-align:justify">The students want to minimize the amount of sweat while walking from their hostels to class. When they enter the sunshine, they begin sweating. The longer they stay in the sun, the more they sweat.</p>
<p style="text-align:justify">Precisely, if the <b>Euclidean</b> distance between points <b>A</b> and <b>B</b> is <b>d</b>, then a student sweats <b>d<sup>2</sup></b> units when going from <b>A</b> to <b>B</b> without stopping anywhere on the way. But if they stop at a shady spot on the way (like a tree), their continuous sun exposure is broken, and they stop sweating immediately! So they can sit in the shade of the tree and cool off before resuming their journey. Once they leave the shade, they start sweating again.</p>
<p style="text-align:justify">For example, if a student goes from his room <b>A<sub>0</sub></b> to class <b>A<sub>n+1</sub></b> while stopping at <b>n</b> trees in between for shade, the total sweat produced is</p>
<p style="text-align:justify"><b>d(A<sub>0</sub>,A<sub>1</sub>)<sup>2</sup> + d(A<sub>1</sub>,A<sub>2</sub>)<sup>2</sup> + …… + d(A<sub>n</sub>,A<sub>n+1</sub>)<sup>2</sup></b></p>
<p style="text-align:justify">Your task is to help the students find a path from their rooms to class in such a way that they sweat the minimum.</p>
<h3>Input</h3>
<p style="text-align:justify">The first line of input contains a single integer T <b>(1 ≤ T ≤ 10)</b>, the number of test cases. Then follow the descriptions of the test cases one by one.</p>
<p style="text-align:justify">For each test case, the first line contains a single integer N <b>(0 ≤ N ≤ 2500)</b> indicating the number of trees on campus. The next N lines each contain a pair of integers denoting the 2D co-ordinates of each tree. The absolute value of each coordinate is less than or equal to 1000. No two trees have the same location. Then there are 2 additional lines – the co-ordinates of the student’s room and the classroom respectively.</p>
<h3>Output</h3>
<p style="text-align:justify">Print a single integer for each test case on a line by itself, the minimum amount of sweat that should be expended when a student goes from his room to class.</p>
<h3>Example</h3>
<pre>
<b>Input:</b>
2
6
8 2
4 0
8 0
4 -1
7 -1
6 -2
2 1
9 2
1
0 0
-1 1
1 -1

<b>Output:</b>
20
4

</pre>