首页 > ACM题库 > HDU-杭电 > HDU 2805-Aligning Two Shapes[解题报告]HOJ
2014
02-17

HDU 2805-Aligning Two Shapes[解题报告]HOJ

Aligning Two Shapes

问题描述 :


The knowledge about Shape from Wikipedia:
Simple two-dimensional shapes can be described by basic geometry such as points, line, curves, plane, and so on. (A shape whose points belong all the same plane is called a plane figure.) Most shapes occurring in the physical world are complex. Some, such as plant structures and coastlines, may be so arbitrary as to defy traditional mathematical description � in which case they may be analyzed by differential geometry, or as fractals.

Rigid shape definition
In geometry, two subsets of a Euclidean space have the same shape if one can be transformed to the other by a combination of translations, rotations (together also called rigid transformations), and uniform scalings. In other words, the shape of a set is all the geometrical information that is invariant to position (including rotation) and scale.
Having the same shape is an equivalence relation, and accordingly a precise mathematical definition of the notion of shape can be given as being an equivalence class of subsets of a Euclidean space having the same shape.

From the message above, we know that we can use the operations of translations, rotations and scaling to align two shapes.
Now we assume that the shapes we describe in the problem is form with a set of points. For example, a shape S = {x1, y1, x2, y2…. xn, yn}.
In the picture below, we use four points to represent a square. The two squares are all centred on the origin (0, 0). After the operation of scaling, S1 is coincides with S2.

To simplify the problem, we suppose two shapes, X1 and X2, centred on the origin (0, 0) initially. That means you can only use the operations of rotations and scaling, but not the translations. We wish to scale and rotate S1 by (s, θ) so as to minimize the sum of the square distances between the points of S1 and S2. Rotation means a two-dimensional object rotates around a center (or point).Scaling means a linear transformation that enlarges or diminishes objects.

输入:

Each test case contains a single integer t (t<=1000), indicating the size of the two shapes (i.e., each shape has t points). The next following t lines each contain two integers (xi, yi) representing the shape of S1, then following t lines stands for the shape of S2. The input is terminated by a set starting with t = 0.

输出:

Each test case contains a single integer t (t<=1000), indicating the size of the two shapes (i.e., each shape has t points). The next following t lines each contain two integers (xi, yi) representing the shape of S1, then following t lines stands for the shape of S2. The input is terminated by a set starting with t = 0.

样例输入:

4
1 1
1 -1
-1 1
-1 -1
2 2
2 -2
-2 2
-2 -2
0

样例输出:

0.000


  1. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。