題意：給你n個矩陣求覆蓋面積。
思路：看了別人的結題報告
給定一個矩形的左下角坐標和右上角坐標分別為:(x1,y1)、(x2,y2)，對這樣的一個矩形，我們構造兩條線段，一條定位在x1，它在y坐標的區間是[y1,y2]，並且給定一個cover域值為1；另一條線段定位在x2，區間一樣是[y1,y2]，給定它一個cover值為-1。根據這樣的方法對每個矩形都構造兩個線段，最後將所有的線段根據所定位的x從左到右進行排序
#include
#include
#include
#include
using namespace std;
#define M 100
#define inf 0x3fffffff
#define maxn 500000*2
struct seg
{
int flag;
double up,down,x;
}line[M*5];
int cmp(seg a,seg b)
{
return a.x=r||tree[id].up<=l) return 0;
if(tree[id].flag)
{
if(tree[id].cover>0)//遞歸到了葉子節點
{
double temp_x=tree[id].x;
double ans=(x-temp_x)*(tree[id].up-tree[id].down);
tree[id].x=x;//定位上一次的x
tree[id].cover+=flag;
return ans;
}
else
{
tree[id].cover+=flag;
tree[id].x=x;
return 0;
}
}
double ans1,ans2;
ans1=insert(id*2,x,l,r,flag);
ans2=insert(id*2+1,x,l,r,flag);
return ans1+ans2;
}
int main()
{
int t,ca=1;
while(scanf("%d",&t)&&t)
{
double x1,x2,y1,y2;
int k=0;
for(int i=0;i
