# Multi-Touch Gesture Classification

With the advent of touch-screen based interfaces, software designers have had to reinvent computer control for finger-based gestures. The most basic task in interpreting a gesture is classifying the touches into one of several possible gestures. This can be difficult because the touches are really blobs of pixels on the screen (not unique points), and gestures involve movement.

We define a *touch* as a connected set of pixels. A
pair of pixels is part of the same touch if they are
horizontally or vertically adjacent. The *touch point*
is the position of a touch. Itâ€™s defined as the average
location of all pixels that are in the set.

A *grip* is the set of all touch points for an image.
The *grip point* is the average location of all touch
points in the grip. For each touch point we define its
*touch vector* as the vector from the grip point to the
touch point. A *gesture* is a pair of grips (initial and
final), and both grips have the same number of touches. There
is a one-to-one correspondence between touches in the initial
and final grip. The correspondence is chosen such that the sum
of squared distances between corresponding touch points is
minimized.

There are three kinds of gestures: pan, zoom, and rotation.
There is a distance associated with each kind. The *pan
distance* is measured between the two grip points. The
*grip spread* is the average distance between each touch
point and the grip point. The *zoom distance* is the
difference between the two grip spreads. The *touch
rotation* is the signed angle (in $[-\pi , \pi ]$ radians) between the
two touch vectors for corresponding touch points. The *grip
rotation* is the average touch rotation. The *rotation
distance* is the arc length of the grip rotation along a
circle with radius equal the grip spread of the initial
grip.

You need to classify the gestures based whether it is a pan, zoom, or rotation. Pick the one which has the greatest associated distance.

## Input

Input is one pair of images, given side-by-side. Both images
are $15\times 30$ pixels,
and there will be a single space on each line separating the
two images. Each image uses `X` to represent
pixels of a touch, and a period (`.`) to
represent no touch. Both images have the same number of
touches, between 1 and 5.

## Output

Print the number of touches and the type of gesture (pan,
zoom, or rotate) as well as the direction of the gesture for
zoom or rotate. The direction for a zoom is `in` if the grip spread of the final grip is smaller
than that of the initial grip, otherwise it is `out`. The direction of a rotate is either `clockwise` or `counter-clockwise`.
All distance comparisons that affect the output will be robust
against numerical error of $10^{-5}$.

Sample Input 1 | Sample Output 1 |
---|---|

.............................. .............................. .............................. .............................. ....XXXX...................... .............................. ....XXXX...................... ............XXXX.............. ....XXXX...................... .............XXX.............. .............................. .............................. .............................. .............................. .............................. .............................. .............................. .............................. .............................. .............................. .............................. .............................. .............................. .............................. .............................. .............................. .............................. .............................. .............................. .............................. |
1 pan |

Sample Input 2 | Sample Output 2 |
---|---|

.............................. .............................. .............................. .............................. .............................. .................XX........... .............................. .......XXX......XXXX.......... .............................. ......XXXX........X........... ........XXX....XXX............ ........X..................... .........XXX...XX............. .............................. .............................. .............................. ............XX................ .............................. ...........XXX................ .............................. .............................. .............................. .............................. ..............XX.............. .............................. .............XXXX............. .............................. ...............XX............. .............................. .............................. |
3 zoom out |

Sample Input 3 | Sample Output 3 |
---|---|

.............................. .............................. .............................. .............................. ........XX.................... .............................. ........XX.................... .................XXXXX........ .............................. ..................XXX......... .............................. .............................. ..XXX................XXX...... .....XX....................... ...XX.................XXX..... .....XXX...................... .............................. .............................. .............................. .............................. .............................. .....XXX...................... .........XXX.................. ......XX......XXXX............ ..........X................... ..............XXXX............ .............................. .............................. .............................. .............................. |
4 rotate counter-clockwise |