2013-08-23 17:35:39Morris
[UVA] 11894 - Genius MJ
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.
| Genius MJ |
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 (
1N105), 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 0 0 1 0 0 1 -2 0 -1 0 -1 -1 2 0 1 1 0 0 -1 0 0
Sample Output
MATCHED NOT MATCHED
題目描述：
插頭跟牆壁上的孔，看能不能匹配，只需考慮 90, 180, 270, 360 度轉，看能不能插上去。
題目解法：
根據向量旋轉公式，選定一個基點全部旋轉 90 度。
比較的時候，先排序所有點，並且考慮平移。
#include <stdio.h>
#include <algorithm>
using namespace std;
struct Pt {
int x, y;
bool operator<(const Pt &p) const {
if(x != p.x)
return x < p.x;
return y < p.y;
}
};
Pt A[100005], B[100005];
void rotate90(Pt A[], int n) {
int i, j, k;
int bx = A[0].x, by = A[0].y;
int tx, ty;
int cos90 = 0, sin90 = 1;
for(i = 0; i < n; i++) {
tx = bx + (A[i].x-bx)*cos90 - (A[i].y-by)*sin90;
ty = by + (A[i].x-bx)*sin90 + (A[i].y-by)*cos90;
A[i].x = tx, A[i].y = ty;
}
}
int main() {
int testcase, n;
int i, j, k;
scanf("%d", &testcase);
while(testcase--) {
scanf("%d", &n);
for(i = 0; i < n; i++)
scanf("%d %d", &A[i].x, &A[i].y);
for(i = 0; i < n; i++)
scanf("%d %d", &B[i].x, &B[i].y);
int matched = 0;
sort(B, B+n);
for(i = 0; i < 4; i++) {
rotate90(A, n);
sort(A, A+n);
int dx = A[0].x - B[0].x;
int dy = A[0].y - B[0].y;
for(j = 0; j < n; j++)
if(A[j].x != B[j].x+dx || A[j].y != B[j].y+dy)
break;
if(j == n)
matched = 1, i = 4;
}
puts(matched ? "MATCHED" : "NOT MATCHED");
}
return 0;
}