B. Affine Mess
Problem ID: affine 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 ho...
Problem Statement
Formatted from the contest statement text, with sample tests broken out into copyable blocks.
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) non- zero 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 ≤ x, 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 – 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?
Input
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.
ICPC 2011 World Finals Problem B: Affine Mess
Output
For each test case, display its case number followed by one of the following three messages:
- “equivalent solutions” to indicate that there are one or more valid transformations, and all of them have the same effect on the whole drawing (no matter what the whole drawing looks like).
- “inconsistent solutions” to indicate that there are several valid transformations, but in general not all of them map the entire drawing in the same way (some drawing is mapped differently by two valid transforma- tions).
- “no solution” to indicate that neither of the first two cases occurs.
A valid transformation is a combination of rotation, translation and scaling (or rotation, scaling and translation) which satisfies the restrictions described above and maps the initial set of red dots to the final set (occupying all three final locations). Follow the format of the sample output.
Sample Tests
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
ICPC 2011 World Finals Problem B: Affine MessCase 1: equivalent solutions
Case 2: inconsistent solutions
Case 3: no solution
Case 4: inconsistent solutions
Case 5: equivalent solutionsEditorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Key Observations
Write the structural observations that make the problem tractable.
State any useful invariant, monotonicity property, graph interpretation, or combinatorial reformulation.
If the constraints matter, explain exactly which part of the solution they enable.
Algorithm
Describe the data structures and the state maintained by the algorithm.
Explain the processing order and why it is sufficient.
Mention corner cases explicitly if they affect the implementation.
Correctness Proof
We prove that the algorithm returns the correct answer.
Lemma 1.
State the first key claim.
Proof.
Provide a concise proof.
Lemma 2.
State the next claim if needed.
Proof.
Provide a concise proof.
Theorem.
The algorithm outputs the correct answer for every valid input.
Proof.
Combine the lemmas and finish the argument.
Complexity Analysis
State the running time and memory usage in terms of the input size.
Implementation Notes
Mention any non-obvious implementation detail that is easy to get wrong.
Mention numeric limits, indexing conventions, or tie-breaking rules if relevant.
Code
C++ solution used for this page.
#include <bits/stdc++.h>
using namespace std;
namespace {
void solve() {
// Fill in the full solution logic for the problem here.
}
} // namespace
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.
Show raw files
competitive_programming/icpc/2011/B-affine-mess/solution.texC++ implementationcompetitive_programming/icpc/2011/B-affine-mess/solution.cppStatement textcompetitive_programming/icpc/2011/B-affine-mess/statement.txtStatement PDFcompetitive_programming/icpc/2011/B-affine-mess/statement.pdfMetadatacompetitive_programming/icpc/2011/B-affine-mess/meta.jsonYear packetcompetitive_programming/icpc/2011/contest_problems.pdf