2013
12-04

# Counting Squares

Your input is a series of rectangles, one per line. Each rectangle is specified as two points(X,Y) that specify the opposite corners of a rectangle. All coordinates will be integers in the range 0 to 100. For example, the line
5 8 7 10
specifies the rectangle who’s corners are(5,8),(7,8),(7,10),(5,10).
If drawn on graph paper, that rectangle would cover four squares. Your job is to count the number of unit(i.e.,1*1) squares that are covered by any one of the rectangles given as input. Any square covered by more than one rectangle should only be counted once.

The input format is a series of lines, each containing 4 integers. Four -1′s are used to separate problems, and four -2′s are used to end the last problem. Otherwise, the numbers are the x-ycoordinates of two points that are opposite corners of a rectangle.

Your output should be the number of squares covered by each set of rectangles. Each number should be printed on a separate line.

5 8 7 10
6 9 7 8
6 8 8 11
-1 -1 -1 -1
0 0 100 100
50 75 12 90
39 42 57 73
-2 -2 -2 -2

8
10000

一道水的线段树，搞了一个晚上，早上脑子清醒过来后终于找到错的地方了~初始化弱智了，在漆黑的环境里面真的不适合写代码。。。

/*

*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define NN 300
#define Swap(a,b) (a=a^b,b=b^a,a=a^b)
struct node{
int r,l,val;
}seg_tree[NN];
int low_x,low_y,high_x,high_y;
int X[NN];
int len_l,len_seg,len_x,val,get_ans;
int cmp(const void *a,const void *b){
return *(int *)a - *(int *)b;
}
void Init(int root,int l,int r)
{
int mid = (l+r)>>1;
seg_tree[root].l = l;
seg_tree[root].r = r;
seg_tree[root].val = 0;
len_seg = len_seg < root ? root : len_seg;
if(r-l == 1)return ;
Init(root*2,l,mid);
Init(root*2+1,mid,r);
}
void insert(int root ,int l,int r){
int mid = (seg_tree[root].l+seg_tree[root].r)>>1;
if(root > len_seg ) return ;
if(l <= seg_tree[root].l && r >= seg_tree[root].r)
seg_tree[root].val = val;
else if(r<=mid)insert(root*2,l,r);
else if(l>=mid)insert(root*2+1,l,r);
else {
insert(root*2,l,mid);
insert(root*2+1,mid,r);
}
return ;
}
void get_seg(int root)
{
if(root > len_seg ) return ;
if(seg_tree[root].val == val){	//用来区分不同区间的Y的长度
get_ans+=(seg_tree[root].r-seg_tree[root].l);
return ;
}
get_seg(root*2);
get_seg(root*2+1);
}
int main()
{
int i,j,ans,x1,x2,y1,y2;
Init(1,0,100);
while(scanf("%d%d%d%d",&x1,&y1,&x2,&y2)){
ans=len_l=len_x=0;
if(x1>x2)Swap(x1,x2);
if(y1>y2)Swap(y1,y2);
X[len_x++] = x1;
X[len_x++] = x2;
while(scanf("%d%d%d%d",&x1,&y1,&x2,&y2)){
if(x1 == -1 || x1 == -2)break;
if(x1>x2)Swap(x1,x2);
if(y1>y2)Swap(y1,y2);
X[len_x++] = x1;
X[len_x++] = x2;
}
qsort(X,len_x,sizeof(int),cmp);
for(i=0;i<len_x-1;i++){
if(X[i] == X[i+1])continue;
val++;//保证了不同区间 线段树中val的值的不同，达到一次建树，多次使用的效果！
for(j=0;j<len_l;j++){
}
get_ans=0;
get_seg(1);
ans += (X[i+1]-X[i])*get_ans;
}
printf("%d\n",ans);
if(x1 == -2)break;
}
return 0;
}

1. 嗯 分析得很到位，确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样：push时，比较要push的elem和辅助栈的栈顶，elem<=min.top()，则min.push(elem).否则只要push（elem）就好。在pop的时候，比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();}，否则{stack.pop();}.

2. “可以发现,树将是满二叉树,”这句话不对吧，构造的树应该是“完全二叉树”，而非“满二叉树”。