Genius MJ

After proving that many of current port types like Serial, USB and ...are useless, MJ designed a new complicated port. His new port turned out to be extremely efficient, but it has one big problem. As the port is produced in diverse shapes for different purposes, people usually try to plug a male cable into a differing female socket, causing the pins to damage. So MJ proposed computer experts to solve this problem. You should write a program to check whether the two parts of a port match. The pins (and holes) of the plug (socket) are given to you as a set of N distinct points in 2D plane. You can translate the points in a set altogether. You can also rotate them around the origin in mul pliers of 90 degrees. (i.e. 90, 180 or 270 degrees) Two parts match each other if a one to one correspondence can be made between the points of the two sets using translation and rotation. Input In the first line there is an integer T (T ≤ 20), the number of pairs of ports to check. Each test begins with an integer N (1 ≤ N ≤ 105), the number of pins (and holes). 2 ∗ N lines follow. First N lines are two integers xi and yi (|xi|, |yi| ≤ 1000), coordinates of i-th pin of plug and next N lines are coordinates of socket in the same format as the plug. Points in each set are distinct. Output For each set output a single word ‘MATCHED’ if the two parts of the port match each other and ‘NOT MATCHED’ if they do not. (Quotes for clarity) Sample Input 2 3 00 10 01 -2 0 -1 0 -1 -1 2 01 10 0 -1 00 Sample Output MATCHED NOT MATCHED