Time limit per test: 0.5 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard
And yet again the Berland community can see that talent is always multi-sided. The talent is always seeking new ways of self-expression. This time genius Kalevich amazed everybody with his new painting “Rectangular Frames”. The masterpiece is full of impenetrable meaning and hidden themes.
Narrow black rectangular frames are drawn on a white rectangular canvas. No two frames have a common point. Sides of each frame are parallel to the sides of the canvas.
The painting is very big and the reduced replica cannot pass the idea of the original drawing. That’s why Kalevich requested that the simplified versions of the masterpiece should be used as replicas. The simplified version is the sequence of the areas of all facets of the original. A facet is a connected enclosed white area within the painting. The areas in the sequence should be written in the non-decreasing order.
Input
The first line of the input contains an integer N(1 ≤ N≤ 60000) — the number of the frames on the drawing. The second line contains integer numbers W_and _H(1 ≤ W, H≤ 108 ).
Let’s introduce the Cartesian coordinate system in such a way that the left bottom corner of the canvas has (0, 0) coordinate and the right top corner has the (W, H) coordinate. The sides of the canvas are parallel to the axes.
The following N_lines contain the description of the frames. Each description is composed of the coordinates of the two opposite corners of the corresponding frame _x_1 , _y_1 , _x_2 , _y_2 (1 ≤ _x_1 , _x_2 < _W; 1 ≤ y_1 , _y_2 < _H; _x_1 != _x_2 , _y_1 != _y_2 ). All coordinates are integers. No two frames have a common point.
Output
Write the desired sequence to the output.
Example(s)
sample input
sample output
1
3 3
2 1 1 2
1 8
矩形不相交，可能会内含。
使用线段树的扫描线，搞出保含关系，然后dfs一遍。
1 /* ***********************************************
2 Author :kuangbin
3 Created Time :2014/5/1 16:10:22
4 File Name :E:\2014ACM\专题学习\数据结构\线段树\SGU319.cpp
5 ************************************************ */
6
7 #include
8 #include <string.h>
9 #include
10 #include
11 #include
12 #include
13 #include <set>
14 #include
Original: https://www.cnblogs.com/kuangbin/p/3703850.html
Author: kuangbin
Title: SGU 319. Kalevich Strikes Back （线段树）
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/546653/
转载文章受原作者版权保护。转载请注明原作者出处！
