41 - ACM ICPC Regional 2005, Hangzhou, Preliminary - 1009
A good OCR (Optical Character Recognition) software would rely on a good number of algorithms. One of the crucial parts is to deskew the given text before it is recognized. The input image is mostly probably from a scanner where the operator does not always ensure that the text is in the correct direction. You will need to devise an algorithm to detect the skew angle of the given image.
To be more realistic for the time frame given to work on the solution, a series
of constraints are guaranteed:
Standard input will contain multiple test cases. The first line of the input is a single integer T (1 <= T <= 10) which is the number of test cases. T test cases follow, each preceded by a single blank line.
The first line contains two integers separated by a single space W and H (512 <= W, H <= 1,024), which are the width and height of the input image (in pixels). The following H lines contain W / 4 characters each, which are the hex representation of the image data. The left most pixel is the most significant bit of the hex string. It is guaranteed that W will be a multiple of 4.
Results should be directed to standard output. Start each case with "Case #:" on a single line, where # is the case number starting from 1. Two consecutive cases should be separated by a single blank line. No blank line should be produced after the last test case.
For each case, output in a line a single integer from in range of -45 to 45, which is the skew angle. Judge's test cases are carefully designed to have integer outputs only, so you do not have to worry about rounding errors.