Akatsuki vs Leaf

4.3

32 votes
Approved, Bit Manipulation, Dynamic Programming, Easy, Matching, Ready
Problem

Akatsuki is planning to attack the Leaf Village to capture Naruto. The Hokage ( Head of the Village ), came to know about the plan and also the number of members, N, in Akatsuki who are going to attack. So, Hokage planned an ambush.

enter image description here

Hokage selected a team of N members ( one for each Akatsuki member ) and named it Leaf. Each member of Leaf can attack exactly one Akatsuki member and an Akatsuki member is NOT attacked by more than one Leaf member. In the ambush there will be N fights ( one of each N members of Leaf and N members of Akatsuki ). You are the leader of Leaf. You know the positions ( x-coordinates and y-coordinates ) of all the Akatsuki members and Leaf members. Your task is to assign each member of Leaf to exactly one member of Akatsuki team such that the sum of the distance between them is minimum. Distance between two points (x1,y1) and (x2,y2) will be equal to |x1x2|+|y1y2|.

Input:
First line contains one integer N, number of Akatsuki members who are going to attack the village.
Next N lines will contain two integers each, X and Y, x-coordinate and y-coordinate of the Akatsuki members.
Next N lines will contain two integers each, X and Y, x-coordinate and y-coordinate of the Leaf members.

Output:
Print the required minimum sum of the distance.

Constraints:
1N20
106X,Y106

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

N=2
So there are 2 Akatsuki members at position (0,0) and (8,8) and 2 Leaf members at position (1,1) and (6,6). There are 2 cases:
Case 1:
Leaf member at (1,1) will fight Akatsuki member at (0,0) and Leaf member at (6,6) will fight Akatsuki member at (8,8).
Sum of distances = ((|10|+|10|)+(|68|+|68|))=(2+4)=6

Case 2:
Leaf member at (1,1) will fight Akatsuki member at (8,8) and Leaf member at (6,6) will fight Akatsuki member at (0,0).
Sum of distances = ((|18|+|18|)+(|60|+|60|))=(14+12)=26

So Case 1 is optimal and minimum sum of distances is 6.

Editor Image

?