题目详情题解（0）讨论（0）提交记录（0）

AT_joi2014ho5.切り取り線 (Cutting)

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

JOI 君的爱好是纸艺制作。今天，JOI 君也打算制作一个纸艺作品。

首先，JOI 君按照设计图，在一张矩形纸上印上了 NN 条切割线。每条切割线都是与纸的边平行的线段。将纸按照所有切割线切开后得到的所有部分都会作为作品中的某个部件。当然，部件数量越多，制作就越困难。JOI 君想知道，按照所有切割线将纸切开后，纸会被分成多少个部分。

输入格式

从标准输入读取以下数据。

  • 第 11 行包含三个整数 W, H, NW,\ H,\ N，用空格隔开。WW 表示纸的横边长度，HH 表示纸的竖边长度，NN 表示切割线的数量。纸的左下、右下、左上、右上分别对应坐标 (0,0), (W,0), (0,H), (W,H)(0, 0),\ (W, 0),\ (0, H),\ (W, H)。
  • 接下来的 NN 行中，第 ii 行（1≤i≤N1 \leq i \leq N）包含四个整数 Ai, Bi, Ci, DiA_i,\ B_i,\ C_i,\ D_i（0≤Ai≤Ci≤W0 \leq A_i \leq C_i \leq W，0≤Bi≤Di≤H0 \leq B_i \leq D_i \leq H），用空格隔开。表示第 ii 条切割线是连接 (Ai,Bi)(A_i, B_i) 和 (Ci,Di)(C_i, D_i) 的线段。该线段与纸的某一边平行，即 Ai=CiA_i = C_i 和 Bi=DiB_i = D_i 中恰好有一个成立。此外，任意两条平行的切割线不会有公共点，任意一条切割线与平行的纸边也不会有公共点。

输出格式

输出一个整数，表示纸被分成的部分数量。

输入输出样例

  • 输入#1

    10 10 5
6 0 6 7
0 6 7 6
2 3 9 3
2 3 2 10
1 9 8 9

    输出#1

    4

  • 输入#2

    13 7 28
1 1 4 1
1 1 1 3
2 2 3 2
2 2 2 3
1 3 2 3
3 2 3 6
4 1 4 6
3 6 4 6
5 1 8 1
5 1 5 6
6 2 7 2
6 2 6 5
7 2 7 5
6 5 7 5
8 1 8 6
5 6 8 6
9 1 12 1
9 1 9 2
9 2 10 2
12 1 12 2
11 2 12 2
10 2 10 5
9 5 10 5
9 5 9 6
11 2 11 5
11 5 12 5
12 5 12 6
9 6 12 6

    输出#2

    5

说明/提示

任务

给定纸的大小和 NN 条切割线的信息，编写程序计算按照这些切割线切割后，纸被分成多少个部分。

限制

所有输入数据满足以下条件。

  • 1≤W≤1 000 000 0001 \leq W \leq 1\,000\,000\,000。
  • 1≤H≤1 000 000 0001 \leq H \leq 1\,000\,000\,000。
  • 1≤N≤100 0001 \leq N \leq 100\,000。

子任务

子任务 1 [5 分]

满足以下条件。

  • W≤1 000W \leq 1\,000。
  • H≤1 000H \leq 1\,000。
  • N≤1 000N \leq 1\,000。

子任务 2 [5 分]

满足以下条件。

  • N≤1 000N \leq 1\,000。

子任务 3 [20 分]

有公共点的不同两条切割线的组数不超过 100 000100\,000。

子任务 4 [20 分]

从任意一条切割线上的点出发，可以沿着若干切割线到达纸的某一边上的点。

子任务 5 [50 分]

无额外限制。

样例解释 1

对于该输入，切割线如下图所示。

因此，纸被切割线分成了 44 个部分。该输入满足子任务 44 的条件。

样例解释 2

对于该输入，切割线如下图所示。

因此，纸被切割线分成了 55 个部分。该输入不满足子任务 44 的条件。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页