ZeroPointSixThreeSix

SRM 689 · 2016-04-01 · by cgy4ever

SRM 689 · 2016-04-01 · by cgy4ever · Geometry

Show categories

Class Name: ZeroPointSixThreeSix

Return Type: int[]

Method Name: replan

Arg Types: (vector<int>, vector<int>, vector<int>)

Problem Statement

Foxland is a perfectly flat country. There are 2*n cities in Foxland. The cities are numbered 0 through 2*n-1. For the purpose of this problem, each city is a point. You are given the coordinates of all cities in the int[]s x and y. For each valid i, city i is located at (x[i], y[i]).

Each city has an airport. There are some flights between those airports. Flight regulations in Foxland specify that each flight must be a round-trip flight between two cities. Additionally, the trajectory of a flight must be the straight line segment between those two cities. (I.e., the planes must always fly along the shortest path.)

Fox Airline is the only airline in Foxland. The airline operates exactly n flights. Each city is served by one of the flights. In other words, there are n disjoint pairs of cities, with each pair of cities being served by one of the n flights.

One day, Fox TV has shown a sci-fi movie in which two airplanes collided. After seeing the movie, many citizens of Foxland became afraid of flying. In order to make them feel safe again, Fox Airline now wants to make sure that their planes will never collide. More precisely, they want to make sure that the trajectories of their n flights are disjoint.

The revenue from a flight is proportional to its length, i.e., to the Euclidean distance between the cities it connects. Your task will be to reroute the flights without losing too much revenue.

You are given the information about the current n flights in the int[] match with 2*n elements. For each valid i, there is a flight between cities i and match[i]. Note that the set of flights described by match can be arbitrary, it does not necessarily maximize the total revenue. Your task is to find a new set of n flights with the following properties:

As before, each of the 2*n cities must be served by one of the n new flights.
The trajectories of the n new flights must be pairwise disjoint.
If the total length of the n old flights is L, the total length of the n new flights must be at least 0.636 * L.

Note that some of the old flights may appear among the new flights. In fact, if the old flights have disjoint trajectories, the new flights may be the same as the old flights.

Return a int[] with 2*n elements, describing the n new flights using the same format as in match. You may assume that there is always at least one valid solution. If there are multiple valid solutions, you may return any of them.

Constraints

x will contain between 4 and 200 elements, inclusive.
x will contain an even number of elements.
x and y will contain the same number of elements, inclusive.
Each element in x and y will be between -100,000 and 100,000, inclusive.
No three points will be on the same line.
match will contain exactly |x| elements.
Each element in match will be between 0 and |x|-1, inclusive.
For each valid i, match[i] != i.
For each valid i, match[match[i]] = i.

Examples

{0,0,1,1}
{0,1,0,1}
{3,2,1,0}
Returns: {1, 0, 3, 2 }

The four cities are located in the vertices of a square. The two old flights correspond to the diagonals of the square. Instead of those, we can choose any two opposite sides of the square as the two new flights. If the total length of the old flights is L, the total lenght of the new flights is L / sqrt(2). This is approximately 0.707 * L , which is clearly at least 0.636 * L.

{0,0,4,4}
{0,3,0,3}
{3,2,1,0}
Returns: {2, 3, 0, 1 }

In this example the four cities are located in the vertices of a 4 by 3 rectangle. Again, the old flights correspond to the diagonals of the rectangle. Their total length is L = 10. Note that this time the two new flights must correspond to the long sides of the rectangle. If you choose the two short sides as the new flights, their total length will be only 0.6 * L, which is less than 0.636. For the two long sides the total length is 0.8 * L.

{0,0,4,4}
{0,3,0,3}
{1,0,3,2}
Returns: {2, 3, 0, 1 }

Here we have the same four cities, but this time the old flights correspond to the short sides of the rectangle. You may return those two flights, but you may also return the two flights that correspond to the long sides of the rectangle. In that case, the revenue from the new flights will actually be greater than the revenue from the old flights. This is allowed.

{-1,1,100,100,1,-1,-100,-100}
{100,100,1,-1,-100,-100,-1,1}
{1,0,3,2,5,4,7,6}
Returns: {1, 0, 3, 2, 5, 4, 7, 6 }

There is no intersection in the old plan, so you can output it.

{-1,1,100,100,1,-1,-100,-100}
{100,100,1,-1,-100,-100,-1,1}
{2,3,0,1,6,7,4,5}
Returns: {7, 2, 1, 4, 3, 6, 5, 0 }

Submissions are judged against all 62 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class ZeroPointSixThreeSix with a public method vector<int> replan(vector<int> x, vector<int> y, vector<int> match) · 62 test cases · 2 s / 256 MB per case