Obviously the problem has many ways to be solved. But I think it is still a tricky one to implement. Don't think my way is short enough but forum doesn't offer any solution at all :-) I think that the description of my source which I sometimes write to certain solutions can help someone to get AC, so I'll leave it here...

/*
 * Let's consider all types of triangles can occure during the
 * cutting process. We can easily notice that there are only 2
 * such type: triangle with sides on 2 diagonal lines and 1
 * straight (vertical or horizontal) or vice-versa (1 and 2).
 * So we can count triangles of these two types separately
 * to get the answer. How can we do this? Let's "draw" our
 * cuts in 2d-array (n-1)x(m-1) and consider a single cell.
 * This cell can be crossed by vertical line from the left and
 * from the right, by horizontal - from top and down and by
 * diagonal - as main and secondary diagonals' directions.
 * So we can code 1 cell with 6-bit value where each bit
 * shows whether corresponding cut goes through the cell or not.
 * Then we can iterate each possible position of triangles
 * of both types on the plate and check whether this triangle really
 * placed here. Small plate size allows us to do this fast enough.
 * And finally, several tricks can be used here:
 *    1. To avoid all intersections located in the middle of any
 *       cell scale all plane in 2 times (multiply each coord by 2).
 *    2. Write only 2 prodecures for recognizing 1 and 2 type of
 *       triangles. Obviously each type can be rotated 4 times on
 *       the plane. Don't try to check these rotations. Simply
 *       make correct recognition of one of them and then solve
 *       problem 4 times rotating the whole plane. After that all
 *       triangles will be counted separalely and in correct way.
 */

Moe reshenie.
Snachala ya ushy tochki peresecheniya otrezkov, dalee dlya vsex tochek opredelyu soedeninu li onu -> sostavlyu matricu smegnosti. Potom ishy ciklu dlinoy 3.

And get WA on test 12.