题目思路

首先将斜率为1和-1的直线分开，由于给出的两点一定在矩形内，所以该直线一定与矩形相交。首先将斜率为-1（或1）的直线先切到矩形上，那么会将矩形分成斜率为-1（或1）的直线条数加一。再将斜率为1（或-1）的直线加入进来，无论与其他直线有没有交点都会产生一个新的矩形。如果该直线与已有的-1（或1）的直线的交点在矩形外，那么将不产生新得矩形，如果交点在矩形内部那么就会产生一个新的矩形。

代码

C++

#include<bits/stdc++.h>

using namespace std;

题目内容

小红是一位著名的锻造家，他经常需要切割钢板来制作各种家具和工艺品。今天，他拿到了一块非常大的矩形钢板，需要将其切割成多个小钢板来制作家具。

为了使得切割后的小钢板能够充分利用，小红需要仔细地规划每一条切割线的位置。他希望每条切割线都是斜着的，因为这样可以得到更多的小钢板。同时，他也想要确保钢板的美观程度，所以每条切割线的斜率只能是 $-1$ 或 $1$。

为了更好地规划切割线的位置，小红先将钢板放到笛卡尔坐标系中，左下角的坐标为 $(0,0)$，左上角的坐标为 $(0,H)$，右下角的坐标为 $(W,0)$，右上角的坐标为 $(W,H)$。然后，他画了 $m$ 条标记线，并将每条标记线的位置表示为两个整数坐标点 $(x_{i,1},y_{i,1})$ 和 $(x_{i,2},y_{i,2})$，这样他就可以用锯子沿着每条标记线进行切割。

现在，小红想知道，如果按照这些标记线进行切割，会得到多少个小钢板。

输入描述

第一行输入两个正整数 $H$ ， $W$ 表示钢板的高度和长度

第二行输入一个正整数 $m$ 表示标记线的条数。

接下来 $m$ 行每行四个正整数$x_{i,1},y_{i,1}, x_{i,2},y_{i,2}$ 表示标记线经过的坐标点。（ $1\le H,W \le 500,1\le m\le 10^3,0 \le x_{i,1},x_{i,2}\le W, 0\le y_{i,1},y_{i,2} \le H$ ）

数据保证$(x_{i,1},y_{i,1}) \neq (x_{i,2},y_{i,2})$

注：如果某条线段出现了多次，按照一次统计即可。

输出描述

输出小钢板的个数。

样例

样例一

输入

1 3
1
1 1 0 1

输出

2

样例二

输入

2 3
2
0 1 0 1
1 0 1 0

输出

3