2015
04-13

Affine Mess

Tess L. Ation ran into a little problem last week when she demonstrated the beta version of her new drawing software.On the screen she had an elegant demonstration design that illustrated every feature of her program; it had taken her hours to produce it. She was just putting the finishing touches on it as a group of potential investors entered the room to see the demonstration.

The presentation went well. Near the end, Tess clicked on a control panel button and told her audience, “This is the ‘snap to grid’ control. It forces control points, such as vertices, to jump to the nearest grid point. Here, let me show you,” and she placed three bright red dots on the screen. Each one appeared at the grid point nearest to where she clicked. (“Luckily all control points in my demo design were already at integer coordinates. But I will have to remember to delete these three red dots before I save my diagram,” she thought to herself.) “Now I’ll step into the next room and get out of your way so you can discuss the system among yourselves and get a closer look at the screen, but please don’t touch anything, since I haven’t saved that file yet.”

A few minutes later, the group joined Tess. One of the visitors stepped up to Tess and said, “I hope you don’t mind, but I wanted to try it myself. Don’t worry, I just played with the x-scale and y-scale controls a little bit.” The next person said, “Sorry if this is a problem, but I really wanted to get a feel for the speed of display, so I just played around with the translation tool.” And a third person said, “I couldn’t resist just one tiny test: I rotated the image just so I could see all of the vertices snap to the nearest grid points after the rotation.”

The person who played with the rotation tool remembered going first, but the other two could not recall their order. The three remembered only a few details of the changes. The x- and y-scaling factors had been (possibly negative) nonzero integers; the center of scaling was the origin (0, 0). The x- and y-translation amounts had been integers. Rotation had been specified by a point with integer coordinates (x, y) on the perimeter of a square of width 20 centered at the origin (hence, -10 <=, y <= 10 and the absolute value of x or y or both was 10). The tool rotated the drawing around the origin such that the positive x-axis would pass through (x, y) afterwards. Snapping took place after this rotation (coordinates with a fractional part of 0.5 were rounded away from zero).

After they left, Tess looked at her design �C it was completely changed! She had not yet implemented the “undo” feature, and she had not saved the diagram prior to giving the demonstration. However, the three identical red dots were still there (transformed to other integer grid locations, of course), and Tess could remember the integer coordinates where she had originally placed them. Obviously, someone else might have altered the drawing without saying anything to her, but she could write a program to see if it was possible to reconstruct the sequence of alterations. Can you too?

The input contains several test cases. Each test case consists of six pairs of integers xi and yi (-500 <=xi, yi <= 500 for 1 <= i <= 6), three pairs per input line. The first three pairs represent the distinct initial locations of the three red dots. The last three pairs represent the distinct final locations of the three dots. The indexing of the pairs in each group of three is not significant: for example, (x1, y1) could have been mapped to any of (x4, y4), (x5, y5) or (x6, y6).
The last test case is followed by a line with six zeros.

The input contains several test cases. Each test case consists of six pairs of integers xi and yi (-500 <=xi, yi <= 500 for 1 <= i <= 6), three pairs per input line. The first three pairs represent the distinct initial locations of the three red dots. The last three pairs represent the distinct final locations of the three dots. The indexing of the pairs in each group of three is not significant: for example, (x1, y1) could have been mapped to any of (x4, y4), (x5, y5) or (x6, y6).
The last test case is followed by a line with six zeros.

3 0 4 0 1 4
-2 -4 -1 3 3 -4
0 1 1 1 2 1
1 2 2 2 3 2
1 0 2 0 3 0
3 3 1 1 2 2
1 0 2 0 3 0
3 2 1 1 2 2
2 3 0 6 1 2
2 3 0 6 1 2
0 0 0 0 0 0

Case 1: equivalent solutions
Case 2: inconsistent solutions
Case 3: no solution
Case 4: inconsistent solutions
Case 5: equivalent solutions

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>

#define PI pair
#define MP make_pair
#define FI first
#define SE second

const double eps = 1e-8;
const double pi = acos(-1.);

using namespace std;

struct point
{
int x, y;
bool operator<( const point r )	const
{
if( x == r.x )	return y < r.y;
return x < r.x;
}
point( int _x = 0, int _y = 0 ) : x(_x), y(_y){}
} A[10], B[10], C[10];

struct T
{
point rot, tra;
} ans[40000];

int snap( double x )
{
if( x < 0 )	return -snap(-x);
return (int)(x+0.5);
}

void rot( double rx, double ry )
{
double d, ang = atan2(ry, rx);
for( int i = 0; i < 3; ++i )
{
d = atan2(A[i].y+0., A[i].x+0.);
double L = sqrt(A[i].x*A[i].x + A[i].y*A[i].y + 0.);
C[i].x = snap(L*cos(d+ang));
C[i].y = snap(L*sin(d+ang));
}
}

int e;
bool line;

void solve( int rx, int ry )
{
rot(rx, ry);

int i, j, k;
int kx, cx, ky, cy;
bool st;

sort(C, C+3);
do
{
st = 0;

if( C[1].x - C[2].x )
{
if( B[1].x-B[2].x == 0 )	continue;
if( (B[1].x-B[2].x)%(C[1].x-C[2].x) == 0 )
{
kx = (B[1].x-B[2].x)/(C[1].x-C[2].x);
cx = B[1].x-C[1].x*kx;
}
else	continue;
}
else if( C[0].x - C[1].x )
{
if( B[0].x-B[1].x == 0 )	continue;
if( (B[0].x-B[1].x)%(C[0].x-C[1].x) == 0 )
{
kx = (B[0].x-B[1].x)/(C[0].x-C[1].x);
cx = B[0].x-C[0].x*kx;
}
else	continue;
}
else
{
if( B[0].x == B[1].x && B[0].x == B[2].x )
{
kx = 1, cx = B[0].x-C[0].x*kx;
st = 1;
}
else	continue;
}

if( C[1].y - C[2].y )
{
if( B[1].y-B[2].y == 0 )	continue;
if( (B[1].y-B[2].y)%(C[1].y-C[2].y) == 0 )
{
ky = (B[1].y-B[2].y)/(C[1].y-C[2].y);
cy = B[1].y-C[1].y*ky;
}
else	continue;
}
else if( C[0].y - C[1].y )
{
if( B[0].y-B[1].y == 0 )	continue;
if( (B[0].y-B[1].y)%(C[0].y-C[1].y) == 0 )
{
ky = (B[0].y-B[1].y)/(C[0].y-C[1].y);
cy = B[0].y-C[0].y*ky;
}
else	continue;
}
else
{
if( B[0].y == B[1].y && B[0].y == B[2].y )
{
ky = 1, cy = B[0].y-C[0].y*ky;
st = 1;
}
else	continue;
}

for( i = 0; i < 3; ++i )
{
if( B[i].x != C[i].x*kx + cx )	break;
if( B[i].y != C[i].y*ky + cy )	break;
}
if( i != 3 )	continue;

ans[e].rot = point(rx, ry);
ans[e].tra = point(kx, ky);
e++;
if( st )	line = 1;
} while( next_permutation(C, C+3) );
}

int main()
{
int cases = 1;
int i, j, k;
double d;

while( 1 )
{
for( i = 0; i < 3; ++i )
scanf("%d %d", &A[i].x, &A[i].y);
if( !A[0].x && !A[0].y && !A[1].x && !A[1].y && !A[2].x && !A[2].y )
break;
for( i = 0; i < 3; ++i )
scanf("%d %d", &B[i].x, &B[i].y);

e = 0;
line = 0;
for( i = -10; i <= 10; ++i )
{
solve(i, 10);	solve(i, -10);
solve(10, i);	solve(-10, i);
}

for( i = 1; i < e; ++i )
{
if( ans[i].rot.x == ans[i-1].rot.x && ans[i].rot.y == ans[i-1].rot.y &&
ans[i].tra.x == ans[i-1].tra.x && ans[i].tra.y == ans[i-1].tra.y )
continue;
if( ans[i].rot.x == -ans[i-1].rot.x && ans[i].rot.y == -ans[i-1].rot.y &&
ans[i].tra.x == -ans[i-1].tra.x && ans[i].tra.y == -ans[i-1].tra.y )
continue;
break;
}

printf("Case %d: ", cases++);
if( e == 0 )	puts("no solution");
else if( line || i < e )	puts("inconsistent solutions");
else	puts("equivalent solutions");
}

return 0;
}

1. for(int i=1; i<=m; i++){
for(int j=1; j<=n; j++){
dp = dp [j-1] + 1;
if(s1.charAt(i-1) == s3.charAt(i+j-1))
dp = dp[i-1] + 1;
if(s2.charAt(j-1) == s3.charAt(i+j-1))
dp = Math.max(dp [j - 1] + 1, dp );
}
}
这里的代码似乎有点问题？ dp(i)(j) = dp(i)(j-1) + 1;这个例子System.out.println(ils.isInterleave("aa","dbbca", "aadbbcb"));返回的应该是false