2013
12-12

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了第一个这种题

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

#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;
}

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