题目内容

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

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

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

题目思路

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

代码

C++

#include<bits/stdc++.h>

using namespace std;