#include #include #include #include #define MAX_LINES 1000 #define EPSILON (0.001) #define ABS(x) ((x)>0 ? (x) : -(x)) /* #define NDEBUG */ /* every end-point of a segment has coordinates [x,y] */ int points_a[2*MAX_LINES][2]; int num_points_a; /* every line contains indexes of its endpoints */ int lines_a[MAX_LINES][2]; int num_lines_a; /* every end-point of a segment has coordinates [x,y] */ int points_b[2*MAX_LINES][2]; int num_points_b; /* every line contains indexes of its endpoints */ int lines_b[MAX_LINES][2]; int num_lines_b; /* global variables for mapping - rotation, expansion, translation */ float sin_val, cos_val; int orig_ax, orig_ay, orig_bx, orig_by; /* global variables for testing, if point lies on a given line */ double seg_a, seg_b, seg_c; /* find the point in the array of points * returns index of the point * if the point do not exists yet, add new point to the array */ int get_point(int x, int y, int *num_points, int (*points)[2]){ int i; for(i=0; i<*num_points; i++){ if( points[i][0]==x && points[i][1]==y ) break; } if (i == *num_points){ points[i][0] = x; points[i][1] = y; (*num_points)++; } return i; } /* returns 1 if sucessfull and 0 in case there is end of input */ int read_logo(int (*points)[2*MAX_LINES][2], int *num_points, int (*lines)[MAX_LINES][2], int *num_lines){ char instruction; int x, y, num; int previous_x, previous_y; int previous_point, new_point; *num_points = 0; *num_lines = 0; /* starting position of plotter is at [0,0] */ previous_point = get_point(0, 0, num_points, (*points)); previous_x = previous_y = 0; while(1) { scanf(" %c ", &instruction); switch (instruction) { case 'Q': return 0; case 'E': return 1; case 'L': scanf(" %d %d ", &x, &y); new_point = get_point(x+previous_x, y+previous_y, num_points, (*points)); (*lines)[*num_lines][0] = previous_point; (*lines)[*num_lines][1] = new_point; (*num_lines)++; previous_point = new_point; break; case 'M': scanf(" %d %d ", &x, &y); previous_point = get_point(x+previous_x, y+previous_y, num_points, (*points)); break; } previous_x = (*points)[previous_point][0]; previous_y = (*points)[previous_point][1]; } } /* Compute constants for mapping points of logo A to logo B providing segment "line_a" which needs to be mapped to segment "line_b". */ void compute_mapping(int line_a, int line_b, int reverse_direction_of_b) { int ax2, ay2, bx2, by2; int vax, vay, vbx, vby; /* compute mapping of points */ orig_ax = points_a[ lines_a[line_a][0] ][0]; orig_ay = points_a[ lines_a[line_a][0] ][1]; ax2 = points_a[ lines_a[line_a][1] ][0]; ay2 = points_a[ lines_a[line_a][1] ][1]; if( reverse_direction_of_b) { orig_bx = points_b[ lines_b[line_b][1] ][0]; orig_by = points_b[ lines_b[line_b][1] ][1]; bx2 = points_b[ lines_b[line_b][0] ][0]; by2 = points_b[ lines_b[line_b][0] ][1]; } else { orig_bx = points_b[ lines_b[line_b][0] ][0]; orig_by = points_b[ lines_b[line_b][0] ][1]; bx2 = points_b[ lines_b[line_b][1] ][0]; by2 = points_b[ lines_b[line_b][1] ][1]; } /* vectors from point 1(origin) to point 2 */ vax = ax2-orig_ax; vay = ay2-orig_ay; vbx = bx2-orig_bx; vby = by2-orig_by; /* rotations -- when centers of coordinate system moved to [0,0] */ /* using matrix for rotations: * [new_x] = [ cos sin ] * [ x ] * [new y] [ -sin cos ] [ y ] */ assert(!(vax==0 && vay==0)); cos_val = (double) (vax*vbx + vay*vby)/(vax*vax+vay*vay); if(vax != 0) sin_val = (double) (cos_val*vay - vby )/vax; else sin_val = (double) vbx/vay; } void map_point(int x, int y, float *new_x, float *new_y) { x = x-orig_ax; y = y-orig_ay; *new_x = cos_val*x+sin_val*y + orig_bx; *new_y = -sin_val*x+cos_val*y + orig_by; } /* Verify similarity of logo A to Logo B, when we try to map segment_a to segment b */ /* Returns 1 if similar, 0 otherwise */ int verify_similarity(int line_a, int line_b, int reverse_direction_of_b) { int x, y, i, seg; int p1, p2, t_p1, t_p2; /* endpoints of segments */ float new_x, new_y, t_x1, t_x2, t_y1, t_y2; /* transformed point coordinates */ int found; /* compute mapping of points */ compute_mapping(line_a, line_b, reverse_direction_of_b); /* verify all segments */ for(seg=0; seg< num_lines_a; seg++) { /* get transformed segment end-points */ p1 = lines_a[seg][0]; p2 = lines_a[seg][1]; map_point( points_a[p1][0], points_a[p1][1], &t_x1, &t_y1); map_point( points_a[p2][0], points_a[p2][1], &t_x2, &t_y2); /* find segment end-points in logo B */ t_p1 = -1; for(i=0;i= *num_lines) { last_seg = lines[last_seg][0]; } (*num_lines)--; lines[last_seg][0] = lines[*num_lines][0]; lines[last_seg][1] = lines[*num_lines][1]; processed_segs[last_seg] = processed_segs[*num_lines]; if(*num_lines != last_seg) lines[*num_lines][0] = last_seg; /* store position, where was the line moved to */ } else { /* start new covering segment */ seg_start_pt = cur_point; } } processed_segs[ cur_seg ]++; covered++; } else { /* end of a cover */ covered--; processed_segs[ cur_seg ]++; if(covered) { /* delete segment */ while ( cur_seg >= *num_lines) { cur_seg = lines[cur_seg][0]; } (*num_lines)--; lines[cur_seg][0] = lines[*num_lines][0]; lines[cur_seg][1] = lines[*num_lines][1]; processed_segs[cur_seg] = processed_segs[*num_lines]; if(*num_lines != cur_seg) lines[*num_lines][0] = cur_seg; /* store position, where was the line moved to */ } else { /* this is last point of the cover */ /* rewrite by covering segment */ while ( cur_seg >= *num_lines) { cur_seg = lines[cur_seg][0]; } lines[cur_seg][0] = seg_start_pt; lines[cur_seg][1] = cur_point; seg_end_pt = cur_point; last_seg = cur_seg; } } } } } } int main(){ int i, j, p1, p2; int similar; while( read_logo( &points_a, &num_points_a, &lines_a, &num_lines_a) && read_logo( &points_b, &num_points_b, &lines_b, &num_lines_b) ) { /* simplifycations of each logo */ simplify_logo(points_a, &num_points_a, lines_a, &num_lines_a); simplify_logo(points_b, &num_points_b, lines_b, &num_lines_b); /* try to map each segment of A to each segment of B and verify similarity for such a mapping/transformation */ /* (mapping vectors instead of segments, thus must try both possible directions of segment in B) */ similar = 0; if (num_lines_a == num_lines_b){ if( num_lines_a == 0) similar = 1; else { for(i=0; i< num_lines_a && !similar; i++) for(j=0; j< num_lines_b && !similar; j++) { similar += verify_similarity( i, j, 0); similar += verify_similarity( i, j, 1); } } } if(similar) printf("YES\n"); else printf("NO\n"); } return 0; }