首页 > ACM题库 > HDU-杭电 > HDU 1542 Atlantis-计算几何-[解题报告] C++
2013
12-12

HDU 1542 Atlantis-计算几何-[解题报告] C++

Atlantis

问题描述 :

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.

输入:

The input file 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.

输出:

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.

样例输入:

2
10 10 20 20
15 15 25 25.5
0

样例输出:

Test case #1
Total explored area: 180.00 

     终于做到了这部分,以前看到这种类型的题只能直接放弃的,现在终于AC了第一个这种题

因为坐标都是浮点数,所以需要对坐标进行离散化(需要插入线段树的坐标进行离散化),为了方便,我直接用了map

     将每个矩形的上下两条水平边存到数组中(得记录这条边是下边还是上边,为了计算覆盖次数,下边记为1,上边记为-1),按y的大小排序;从y最小的边开始向上扫描,首先将一条边插入线段树,然后得到当前当前扫描线所在位置的覆盖到的边的总长,                                                                                                  

第一次是A1B1边插入到书中,扫描线覆盖到的边的总长就是A1B1,再拿他乘以当前高度和下一条边的高度差,得到底下那个矩形的面积

第二次是第二条黑边插入线段树,这时扫描到的总长度为A2B2,再拿他乘以当前高度和下一条边的高度差,得到中间那个长矩形的面积

第三次是A1B1的对边插入线段树,因为这条边是上边,所以覆盖次数会被-1,挺次,原先线段树中被A1B1覆盖的部分会被-1,所以,此时线段树中能够计算得到扫面线扫到的总长为A3B3的长度,再拿他乘以当前高度和下一条边的高度差,得到最上面那个矩形的面积

三者相加就是总面积了

插入的时候也得注意,不是根据坐标计算出其离散值就当做区间直接插入,而是要将右坐标的离散值减1,这样做的原因是:

这样的两条线段其实没有相互覆盖,但是如果r不减1的话,他们就会变成彼此覆盖的了……在这颗线段树中,一个点其实表示一个区间

这么做了以后,在计算时只要再把r加上1就好了

以下是代码:

#include <cstdio>
#include <cstring>
#include <map>
#include <algorithm>
using namespace std;
const int MAX = 210;
struct line
{
    double l,r,h;
    int f;
    line(){}
    line(double a,double b,double c,int d):l(a),r(b),h(c),f(d){}
}a[MAX<<1];
double sum[MAX<<2],x0[MAX];
int cov[MAX<<2];
map<double,int>m;
int cmp(const line &a,const line &b)
{
    return a.h<b.h;
}
void push_up(int l,int r,int rt)
{
    if(cov[rt]) sum[rt] = x0[r+1] - x0[l];
    else if(l==r) sum[rt]=0;
    else sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void update(int c,int L,int R,int l,int r,int rt)
{
    if(L<=l&&R>=r)
    {
        cov[rt]+=c;
        push_up(l,r,rt);
        return;
    }
    int mid = r+l>>1;
    if(L<=mid) update(c,L,R,l,mid,rt<<1);
    if(R>mid) update(c,L,R,mid+1,r,rt<<1|1);
    push_up(l,r,rt);
}
int main()
{
    int n;
    double x1,x2,y1,y2;
    int cas = 0;
    while(scanf("%d",&n)&&n)
    {
        int cnt = 0;
        int flag = 0;

        for(int i=0; i<n; i++)
        {
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            a[cnt++] = line(x1,x2,y1,1);
            a[cnt++] = line(x1,x2,y2,-1);
            if(m[x1]==0) m[x1] = ++flag;
            if(m[x2]==0) m[x2] = ++flag;
        }
        map<double,int>::iterator iter;
        int k = 0;
        for(iter=m.begin(); iter!=m.end(); iter++)
        {
            x0[++k] = iter->first;
            iter->second = k;
        }
        sort(a,a+cnt,cmp);
        double ans = 0;
        memset(sum,0,sizeof(sum));
        memset(cov,0,sizeof(cov));
        for(int i=0; i<cnt-1; i++)
        {
            int l = m[a[i].l];
            int r = m[a[i].r]-1;
            update(a[i].f,l,r,1,flag,1);
            ans+=(a[i+1].h-a[i].h)*sum[1];
        }
        printf("Test case #%d\n",++cas);
        printf("Total explored area: %.2lf\n\n",ans);
        m.clear();
    }
    return 0;
}

解题报告转自:http://blog.csdn.net/cen5bin/article/details/7833089


  1. #include <stdio.h>
    int main(void)
    {
    int arr[] = {10,20,30,40,50,60};
    int *p=arr;
    printf("%d,%d,",*p++,*++p);
    printf("%d,%d,%d",*p,*p++,*++p);
    return 0;
    }

    为什么是 20,20,50,40,50. 我觉得的应该是 20,20,40,40,50 . 谁能解释下?

  2. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  3. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。