CF31D.Chocolate
普及+/提高
通过率:0%
时间限制:2.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Bob has a rectangular chocolate bar of the size W × H. He introduced a cartesian coordinate system so that the point (0, 0) corresponds to the lower-left corner of the bar, and the point (W, H) corresponds to the upper-right corner. Bob decided to split the bar into pieces by breaking it. Each break is a segment parallel to one of the coordinate axes, which connects the edges of the bar. More formally, each break goes along the line x = x__c or y = y__c, where x__c and y__c are integers. It should divide one part of the bar into two non-empty parts. After Bob breaks some part into two parts, he breaks the resulting parts separately and independently from each other. Also he doesn't move the parts of the bar. Bob made n breaks and wrote them down in his notebook in arbitrary order. At the end he got n + 1 parts. Now he wants to calculate their areas. Bob is lazy, so he asks you to do this task.
鲍勃有一块尺寸为 W×H 的矩形巧克力。他建立了一个笛卡尔坐标系,使得点 (0,0) 对应巧克力左下角,点 (W,H) 对应右上角。鲍勃决定通过折断的方式将巧克力分割成若干小块。每次折断都是一条平行于坐标轴的线段,且连接巧克力当前某一块的两条边界。更准确地说,每次折断沿直线 x=xc 或 y=yc 进行,其中 xc 和 yc 均为整数;该折断必须将当前某一块巧克力分成两个非空的部分。每当鲍勃将某一块折断为两块后,他便独立地、分别地对这两块继续进行后续折断操作;并且他不会移动任何一块巧克力的位置。鲍勃总共进行了 n 次折断,并将这些折断记录在笔记本中,顺序是任意的。最终他得到了 n+1 块巧克力。现在他想计算每一块的面积。由于鲍勃很懒,他请你来完成这项任务。
输入格式
The first line contains 3 integers W, H and n (1 ≤ W, H, n ≤ 100) — width of the bar, height of the bar and amount of breaks. Each of the following n lines contains four integers x__i, 1, y__i, 1, x__i, 2, y__i, 2 — coordinates of the endpoints of the i-th break (0 ≤ x__i, 1 ≤ x__i, 2 ≤ W, 0 ≤ y__i, 1 ≤ y__i, 2 ≤ H, or x__i, 1 = x__i, 2, or y__i, 1 = y__i, 2). Breaks are given in arbitrary order.
It is guaranteed that the set of breaks is correct, i.e. there is some order of the given breaks that each next break divides exactly one part of the bar into two non-empty parts.
第一行包含三个整数 W、H 和 n(1 ≤ W, H, n ≤ 100),分别表示巧克力条的宽度、高度以及断裂次数。接下来的 n 行每行包含四个整数 xi,1、yi,1、xi,2、yi,2,表示第 i 次断裂的两个端点坐标(满足 0 ≤ xi,1 ≤ xi,2 ≤ W,0 ≤ yi,1 ≤ yi,2 ≤ H,且要么 xi,1 = xi,2,要么 yi,1 = yi,2)。所有断裂按任意顺序给出。
保证所给断裂集合是合法的,即存在某种顺序,使得每次后续断裂恰好将巧克力条的某一个部分分成两个非空的部分。
输出格式
Output n + 1 numbers — areas of the resulting parts in the increasing order.
输出 n+1 个数——所得各部分的面积,按升序排列。
输入输出样例
输入#1
2 2 2 1 0 1 2 0 1 1 1
输出#1
1 1 2
输入#2
2 2 3 1 0 1 2 0 1 1 1 1 1 2 1
输出#2
1 1 1 1
输入#3
2 4 2 0 1 2 1 0 3 2 3
输出#3
2 2 4
输入解题思路,AI测评打分。不知道怎么写?