小A和小B一起去电影院看电影，电影院的座位有N排，编号为1..N，每排有M个座位，编号为1..M，其中有些座位已经有人坐了。他们俩要找两个同一排相邻的两个无人的座位，问有多少个可行方案。
输入
三个整数N,M,K。
以下K行，每行两个数X，Y，表示第X排第Y个座位有人，同一个座位至多只出现一次。
输出
一个数，表示他们俩可以选择的方案数。
样例
输入1  复制
2 3 2
1 2
2 3
输出1  复制
1
输入2  复制
4 7 1
1 1
输出2  复制
23
提示
对于30%的数据，N,M<=100。
对于100%的数据，1<=N,M<=1,000,000,000，1<=K<=47。

没想出什么好的算法，用的是最普通的方法

#include <iostream>
#include <algorithm>
#include <iterator>
#include <utility>
using namespace std;

struct foo
{
    size_t x, y;

    friend std::istream& operator>> (std::istream& is, foo& obj )
    {
        return is >> obj.x >> obj.y;
    }
    friend bool operator<( const foo& lhs, const foo& rhs ) noexcept
    {
        return std::tie(lhs.x,lhs.y) < std::tie(rhs.x,rhs.y);
    }
    friend size_t bulk( const foo& lhs, const foo& rhs, size_t m ) noexcept
    {
        auto foo = [](size_t delta) { return delta<2 ? 0 : delta-2; };
        return lhs.x==rhs.x ? foo(rhs.y-lhs.y) : foo(m+1-lhs.y) + (rhs.x-lhs.x-1)*(m-1) + foo(rhs.y-0);
    }
};

int main( void )
{
    // 输入
    size_t n,m,k;
    foo s[1+47+1]; // 题目中交代过 1<=K<=47
    cin >> n >> m >> k;
    copy_n( istream_iterator<foo>(cin), k, s+1 );

    // 开始干活
    sort( s+1, s+1+k ); // 题目中没说过一定按照顺序输入
    s[0].x=1, s[0].y=0;
    s[k+1].x=n, s[k+1].y=m+1;
    size_t sum = 0;
    for( size_t i=0; i!=k+1; ++i )
        sum += bulk( s[i], s[i+1], m );

    // 输出
    cout << sum << endl;
}