All submissions for this problem are available.
At IIT Kanpur, students take the course TA201 - Manufacturing Processes as part of the compulsory curriculum. Working on CNC (Computer Numerical Control) machines is part of the course, where jobs like cutting metal sheets and rods with desired dimensions can be done by machines which have been programmed by a computer before.
In one of the lab sessions, students are required to cut a 2-D metal sheet using a LSM Laser Machine. As an experimental setup, a very long metal rectangular sheet is placed on a table with the LSM Machine mounted over the sheet. The metal sheet can be considered as the 2-dimensional Euclidean plane. The length of the sheet is along the x-axis and its breadth is along the y-axis. The apparatus of the machine is such that there is a rod which moves along x-axis (from left to the right) cutting the sheet underneath using two lasers attached to the rod. The rod is aligned along the sheet’s breadth (y-axis) and is moved along the direction perpendicular to its own length (along the length of the sheet, i.e. x-axis). The two laser beams attached to the rod can slide along the rod’s length (y-axis).
For the experiment, all students are given a sheet with N distinct points marked on it. Each point is of the form (x,y) where the bottom left corner of the sheet is the origin. The rod is restricted to move only from left to right and the two lasers are kept ‘on’ during the rod’s movement, thus leaving a continuous cut on the metal sheet. For the lab task, students have to cut out a closed polygonal shape. The polygon should be such that it has all the given N points on its boundary and all the vertices of the polygon must belong to the same set of the given N points. The lasers used in the LSM machine are peculiar. The amount of energy consumed by the laser while moving between any 2 of the given points is equal to the square of the length of the straight line along the sheet joining the 2 points. Students have to program the LSM machine to move the lasers along the moving rod and cut the sheet in such a way that the total energy consumed by the 2 lasers is the minimum. Your task is to find out the minimum total energy consumed by the 2 lasers combined.
The first line of input contains T <= 10, the number of test cases. Each test case begins with the first line containing N (2 <= N <= 1000), the number of points on the sheet given to the students. Each of the next N lines contains the points marked on the sheet as two space separated integers x y with 0 <= x,y <= 10^4.
For each test case, output a single line containing the minimum total power consumed by the 2 lasers.
Input: 2 5 0 0 2 0 4 0 5 9 6 0 2 3 4 4 3 Output: 196 4
|Time Limit:||0.1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP 4.3.2, CPP 6.3, CPP14, GO, JAVA|
Fetching successful submissions
If you are still having problems, see a sample solution here.