UVA 11538 - Chess Queen

Problem link

Keyword: finding pattern, ad hoc

Algorithm:

Since queen can attack in horizontal, vertical, and diagonal direction, we can find all the ways in these 3 situations.
For horizontal attacks, there are h*w cells, each of which can attack w-1 cells, so the total is h*w*(w-1).
For vertical attacks, each cell can attack h-1 cells so the total is h*w*(h-1).
The hardest part of this problem is diagonal attacks. Using brute force method to calculate diagonal attacks is slow and you may (which implies you can still use this method, but your solution will have to be more efficient) get TLE.
For diagonal attacks, we only consider those attacks whose "slope" is negative (or positive) because the amount is equal and we can get it by doubling it.
To calculate the ways, we can use a sigma operator to find that. For diagonal with N cells, a queen can be put on N cells and N-1 cells are attacked, and therefore N*(N-1) ways are found.
At last you'll be able to organize them into a formula.

Ah! What a difficult explanation!

Code:

#include<cstdio>
#include<algorithm>
using namespace std;

int main()
{
    long long int row, col;

    while( scanf( "%lld %lld", &row, &col ) && row )
    {
        if( row < col )
            swap( row, col );
        long long int ans = row * col * ( row + col - 2 );
        if( row == col )
            ans += 2 * ( col * ( col+1 ) * ( 2*col+1 ) / 3 - ( 1+col ) * col - row * ( row - 1 ) );
        else
            ans += 2 * ( col * ( col+1 ) * ( 2*col+1 ) / 3 - ( 1+col ) * col + ( col-1 ) * ( row - col - 1 ) * col );
        printf( "%lld\n", ans );
    }

    return 0;
}