信息学国家集训队作业0084-oil

1、题目 0084 Oil（倒油容器）题目来源：Finals02者：一、英文原文Toil for Oile a high-technology industry. With improved drillingProspecting for new sourtechnology it hasof oil hase economically viable to seek out ever smaller and harder to reachdeits of oil. However, using exploratory drilling to locate these deits is not co

2、st-efficient, soresearchers have developed methods to detect oil indirectly.One such method to detect oil is sonar, which uses reflected sound waves to locate caves inunderground rock formations. Determining how much oil can be contained in such a cave is a difficult problem.In this problem, you wil

3、l be given some cross-sections of underground caves, represented bypolygonch as the ones shownhe figure. Some of the pos bounding the polygon may beholes through which oil can seep outo the surrounding rock (represented by black circleshefigure). Given the polygonal shof the cave and theitions of th

4、e holes, you must computetheum amount of oilt could behe cave (shown as gray shaded areashe figure).This amount is limited by the factt, in any connected body of oil, the oil level can never beabove a hole, since it would draino the surrounding rock instead.InputThe input contains several cave descr

5、iptions, each in the form of a polygont specifies across-section of a cave. Theline of each description contains a singleeger n, representingthe number of pos on the polygon (3 n 100).Each of the following n lines contains threeegers xi, yi, hi. The values (xi, yi) give theitionsof the pos on the bo

6、undary of the polygon in counterclockwise order. The polygon issimplet is, it does not cross or touch itself. The value of hi is equal to 1 if the pois a holethrough which oil can seep out, and 0 otherwise. The “upward” direction in each case is theitive y-axis.The input is terminated by a zero on a

7、 line by itself.OutputFor each cave description, prits sequence number (starting with 1) followed by its oil capacity.Approximate the oil capacity by the area within the given cross-sectiont may contain oil,rounded to the nearesteger. Use the formathe example output given below.Place a blline after

8、each test case.Sample InputOutput for the Sample Input410 0 05 10 10 20 0-10 0 0110 6 06 06 4 04 6 08 10 010 8 012 10 08 14 10Cave 1: Oil capacity = 150Cave 2: Oil capacity = 27二、中文翻译三、初步情况离散化即可。昆非矩形的离散化散化和并查集侯启明曾经做过但是因程序太复杂而没有调出来璟似乎可以根据连通器原理依次确定每个漏油点。从高到低，从每个孔出发，用水平线切割多边形，取下面的部分。但有细节没考虑清楚。定义所有顶点和漏油

9、点为事件点，然后从下往上处理。还是麻烦。这道几何题可以用水平线段进行切割，端点下方是否有漏油点每一条水平线段，判断是否漏油，即判断两首先，使每一种物质连续也就是给定了一段必须连续的星球。依次处理每一种物质，就是将这些交、并的过程，如何利用合适的算法和数据结构做好这个工作值得。想法是模拟水漏出来，把所有顶点和洞点按照从高到低排下来，依次检索。过每一个点作一条水平直线切割多边形，取下方的部分，多边形可能会变成多个子多边形，依次处理就是了。关键就是直线切割多边形的过程，这是应该是有标准算法的。过每一点作一条水平线，作出这条线与多边形的其他交点；根据已知的“不可的点”（即若水灌溉到其上方，则水必然会溢

10、出），求出所有的“不可可的点”下方的区域面积（分成若干块小梯形或三角形）。的点”，然后计算在“不对多边形边界上的每一个已知点，作过它的水平线，求出这条水平线与多边形的其它交点。对每一个已知的不可的点，用回溯法标记所有其上方的点“不可”（若某点与它在同一水平线上，则若此二点连线在多边形内部，则这一点也标记；若连线在多边形外部，则考虑分别过这二点的二条多边形的边，若这两条边的交点在此二点的下方，则这一点也标记，否则不标记）。然后，根据所有的点，按照纵坐标从小到大的顺序依次考虑每块区域（梯形或三角形），若区域下部的点没有“不可考虑了每块区域后，就得到所求的总面积。”标志，则将其面积计入总面积；否则不

11、计。了一个方法：首先，按逆时针的顺序给每条边规定方向。从上到下处理每个点 P（包括多边形的点和漏油点），作一条经过 P 的水平直线 l。如果直线与一条向下的边a 相交，则分别向左、向右找出与a 最邻近的向上的边 b,c，如果 l,a,b 以及a 和 b 夹着的边组成的多边形中无漏油点，则该多边形可以的边组成的多边形也同样处理。油。对 l,a,c 以及a 和c 夹着第 1 个图，原多边形；第 2 个图，将多边形的边有向化；第 3、4 个图，从上到下枚举，找出一个适合的积油点。离散化！按纵坐标离散，洞也要算进来，从低到高来判断每一阶段中哪些部分可以装油，每一部分的判断与它下面的部分有关，如果与他相

12、连的部分中有空的情况，那么这一部分就不能装油，或者，它的一边上有洞，此部分也不能装油，而题目中的阶段中有些部分可能是从底部连通的，那么就是说如果其中有一段不能装油的话，其他的与其相同的部分都不能装油，而不管其它部分的下面是否有空部分。如下图：2看上图，第三阶段的 2 部分的下面非空，但是 2 部分的底部有洞所以 2 部分不能装油，而同时虽然 1 部分的下面也有油但是 1，2 底部是相通的，所以 1 部分同样不能有油。这些相通的情况如何解决呢？很好解决，把每个部分都标记一下，如果标记相同的话，他们的底部是相通的。但是这样还是有不好处理的地方就是可能两个标号不同的部分连起来了，那么这两部分显然要归

13、于一类，但是要修改标号的复杂度就比较高，所以可以改个数少的那部分标号，总修改的复杂度为 O(nlogn),也可以通过并查集来做，都是比较可以的处理方法。这些东西确定的话，问题基本解决了，此算法的复杂度基本为O(N2 )，但可以优化。林希德将所有边按照左端点 x 坐标排序，然后过每一个容器顶点和漏油一条水平直线，如图：从下到上依次察看每两条相邻的水平直线，考虑它们和容器边组成的若干梯形（三角是特殊的梯形），给这些梯形编号、求出它们的面积、并上下底边（因为容器边已排序，所以该步复杂度为 O(n2)）。根据上下底边，求出哪些梯形是直接连通的，用邻接链表这种连通关系。定义所谓“满油状态”是指梯形内部装

14、满了石油，“满油状态”的相对含义是“空油状态”；所谓“漏油状态”是指再次往梯形内倒石油时油会从某处泄漏，“漏油状态”的相对含义是“载油状态”；注意，一个梯形是否“满油”和它是否“漏油”没有必然联系。初始时，设置所有梯形为“空油”且“载油”状态，然后从下到上依次察看每个梯形 A。对于高度高于 A 的任何梯形 B，在察看梯形A 之前不进行任何关于 B 的操作。如果梯形 A 下底边有漏油孔或者和 A 连通（所谓“连通”是指当前连通，也就是不考虑任何高度高于 A 的梯形 B 时的连通关系，它包括直接连通和间接连通。连通关系的求解用并查集实现）的某个梯形处于“漏油状态”，那么 A 仍然是“空油状态”；否则 A 是“满油状态”。在察看完所有和 A 处于同一高度的梯形 C 是否“满油”以后，回过头来，再把所有上底边有漏油孔的 C 设为“漏油状态”，其它的 C 仍保持“载油状态”。最后，根据每个梯形是否“满油”可以知道容器存油总面积。粗略估计，空间复杂度 O(n2)，时间复杂度 O(n2)。1Y 轴离散，（如右图所示），容易证明：由多边形边界及水平划分线分离出的每个梯形（三角形看成是上底或下底长为 0）要么里面都充满油要么都不充满油。只要知道任意一个梯形是否充满油，就可以轻而易举的计算出