POJ 1151 Atlantis 解题报告

一、问题描述

Description

There are several ancient Greek texts that contain descriptions of the fabled island Atlantis. Some of these texts even include maps of parts of the island. But unfortunately, these maps describe different regions of Atlantis. Your friend Bill has to know the total area for which maps exist. You (unwisely) volunteered to write a program that calculates this quantity.

Input

The input consists of several test cases. Each test case starts with a line containing a single integer n (1 <= n <= 100) of available maps. The n following lines describe one map each. Each of these lines contains four numbers x1;y1;x2;y2 (0 <= x1 < x2 <= 100000;0 <= y1 < y2 <= 100000), not necessarily integers. The values (x1; y1) and (x2;y2) are the coordinates of the top-left resp. bottom-right corner of the mapped area.
The input file is terminated by a line containing a single 0. Don't process it.

Output

For each test case, your program should output one section. The first line of each section must be "Test case #k", where k is the number of the test case (starting with 1). The second one must be "Total explored area: a", where a is the total explored area (i.e. the area of the union of all rectangles in this test case), printed exact to two digits to the right of the decimal point.
Output a blank line after each test case.

Sample Input

2

10 10 20 20

15 15 25 25.5

0

Sample Output

Test case #1

Total explored area: 180.00

 

二、解题思路

题目意思是求N个矩形并的面积。这里采用的是矩形切割的方法：即每放入一个矩形都判断是否与已经存在的矩形相交，如果相交则把与之相交的矩形切割成多个小矩形，然后放入矩形列表里，同时删除原来的矩形。所有矩形都放进去后再遍历一次列表，求所有矩形面积的和。

在这里要解决两个问题：

1、如何判断矩形是否相交？

2、怎么样进行矩形切割？

对于第1个问题可采用这个方法解决：http://blog.chinaunix.net/u3/105033/showart_2227872.html

第2个问题的解决方法参考IOI国家集训队论文《剖析线段树与矩形切割》。

三、代码

 

 

#include<iostream>
#include<list>
using namespace std;
struct rectangle
{
    double x1,y1;
    double x2,y2;
};
double dmax(double a,double b)
{
    if(a>b)
        return a;
    else
        return b;
}
double dmin(double a,double b)
{
    if(a>b)
        return b;
    else
        return a;
}
//求矩形面积
double area(rectangle r)
{
    return (r.x2-r.x1)*(r.y2-r.y1);
}
//判断两矩形是否相交
bool isInter(rectangle r1,rectangle r2)
{
    rectangle r3;
    r3.x1=dmax(r1.x1,r2.x1);
    r3.y1=dmax(r1.y1,r2.y1);
    r3.x2=dmin(r1.x2,r2.x2);
    r3.y2=dmin(r1.y2,r2.y2);
    if(r3.x2 > r3.x1 && r3.y2 > r3.y1)
        return true;
    else
        return false;
}
list<rectangle> rl;
int N;
//添加一个新的矩形
void Add(double x1,double y1,double x2,double y2)
{
    rectangle r;
    r.x1=x1;
    r.x2=x2;
    r.y1=y1;
    r.y2=y2;
    rl.push_back(r);
}
//矩形分割
void Cut(rectangle r1,rectangle r2)
{
    double k1,k2,k3,k4;
    k1=dmax(r1.x1,r2.x1);
    k2=dmin(r1.x2,r2.x2);
    if(r1.x1 < k1)
        Add(r1.x1, r1.y1, k1, r1.y2);
    if(k2 < r1.x2)
        Add(k2, r1.y1, r1.x2, r1.y2);

    k3=dmax(r1.y1,r2.y1);
    k4=dmin(r1.y2,r2.y2);
    if(r1.y1 < k3)
        Add(k1, r1.y1, k2, k3);
    if(k4 < r1.y2)
        Add(k1, k4, k2, r1.y2);
}

int main()
{
    int i;
    double s;
    int c=0;
    while(scanf("%d",&N))
    {
        if(N==0)
            break;
        c++;
        s=0.0;
        rl.clear();
        for(i=0;i<N;++i)
        {
            rectangle rec;
            scanf("%lf%lf%lf%lf",&rec.x1, &rec.y1,&rec.x2,&rec.y2);
            list<rectangle>::iterator it;
            for(it=rl.begin();it!=rl.end(); )
            {
                if(isInter(rec,*it)==true)//相交

                {
                    Cut(*it,rec);
                    list<rectangle>::iterator del;
                    del=it;
                    it++;
                    rl.erase(del);
                    continue;
                }
                ++it;
            }
            rl.push_back(rec);
        }
        for(list<rectangle>::iterator it=rl.begin(); it!=rl.end(); ++it)
        {
            s+=area(*it);
        }
        printf("Test case #%d\nTotal explored area: %.2f\n\n",c,s);
    }
    return 0;
}