hdu 1255 커버 면적 직사각형 면적 교차

Problem Description
평면 에 있 는 몇 개의 사각형 을 지정 하여 이 사각형 에 적어도 두 번 덮 인 구역 의 면적 을 구하 십시오.
 
Input
데 이 터 를 입력 하 는 첫 번 째 줄 은 정수 T (1 < = T < = 100) 로 테스트 데이터 의 수량 을 대표 합 니 다. 각 테스트 데이터 의 첫 번 째 줄 은 정수 N (1 < = N < = 1000) 이 고 사각형 의 수량 을 대표 합 니 다. 그 다음 에 N 줄 의 데 이 터 를 포함 합 니 다. 각 줄 은 네 개의 부동 소수점 을 포함 하고 평면 상의 한 사각형 을 대표 하 는 왼쪽 상단 좌표 와 오른쪽 하단 좌표, 사각형 의 상하 변 과 X 축 이 평행 합 니 다.좌우 변 과 Y 축 은 평행 이다. 좌표 의 범 위 는 0 에서 100000 까지 이다.
주의: 이 문제 의 입력 데이터 가 비교적 많 으 므 로 scanf 로 데 이 터 를 읽 는 것 을 추천 합 니 다.
 
Output
각 그룹의 테스트 데이터 에 대해 서 는 이 사각형 에 최소 두 번 덮 인 구역 의 면적 을 계산 하 십시오. 결 과 는 두 개의 소 수 를 유지 합 니 다.
 
Sample Input
2 5 1 1 4 2 1 3 3 7 2 1.5 5 4.5 3.5 1.25 7.5 4 6 3 10 7 3 0 0 1 1 1 0 2 1 2 0 3 1
 
Sample Output
7.63 0.00
//
#include #include #define MAXN 2015 using namespace std; //좌 표 는 부동 소수점 double y [MAXN * 2];struct lovekid{  double left,right,len,crossLen;  lovekid *leftSon,*rightSon;  int cover; }tree[MAXN*2],*Root; struct line{     double x,y1,y2;     int cover;     bool operator         return x     } }point[MAXN*2]; int idx; lovekid *CreatKid(){  lovekid *p;  p=&tree[idx++];  p->cover=0;  p->len=p->crossLen=0;  p->leftSon=NULL;  p->rightSon=NULL;  return p; } lovekid *CreatLoveKid(int left,int right){  lovekid *root=CreatKid();  root->left=y[left];  root->right=y[right];  if(right-left>1){   int mid=(left+right)>>1;   root->leftSon=CreatLoveKid(left,mid);   root->rightSon=CreatLoveKid(mid,right);  }  return root; } void GetLen(lovekid*root){  root->len=0;  if(root->cover>0)   root->len=root->right-root->left;  else if(root->leftSon!=NULL)   root->len=root->leftSon->len+root->rightSon->len; } void GetCrossLen(lovekid*root){  root->crossLen=0;  if(root->cover>1)   root->crossLen=root->right-root->left;  else if(root->leftSon!=NULL){   if(root->cover>0)    root->crossLen=root->leftSon->len+root->rightSon->len;   else root->crossLen=root->leftSon->crossLen+root->rightSon->crossLen;  } } void UpdateLen(lovekid*root){  GetLen(root);  GetCrossLen(root); } void Update(lovekid*root,line t){     if(root->left==t.y1&&root->right==t.y2){         root->cover+=t.cover;         UpdateLen(root);         return;     }     if(t.y1>=root->leftSon->right)         Update(root->rightSon,t);     else if(t.y2<=root->rightSon->left)         Update(root->leftSon,t);     else{         line tmp=t;         tmp.y2=root->leftSon->right;         Update(root->leftSon,tmp);         tmp=t;         tmp.y1=root->rightSon->left;         Update(root->rightSon,tmp);     }     UpdateLen(root); } int main(){  //freopen("C:\\Users\\loveKid\\Desktop\\in.txt","r",stdin);  int N,cas,i,j;  double x1,x2,y1,y2,ans;  scanf("%d",&cas);  while(cas--){   scanf("%d",&N);      idx=j=0;   ans=0;      for(i=0;i          scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);          point[j].x=x1;          point[j].y1=y1;          point[j].y2=y2;          point[j].cover=1;          y[j]=y1;          point[j+1].x=x2;          point[j+1].y1=y1;          point[j+1].y2=y2;          point[j+1].cover=-1;          y[j+1]=y2;      }      sort(y,y+j);      sort(point,point+j);      Root=CreatLoveKid(0,j-1);      Update(Root,point[0]);      for(i=1;i          ans+=Root->crossLen*(point[i].x-point[i-1].x);           Update(Root,point[i]);      }      printf("%.2lf",ans);  }  return 0; }