Atlantis (hdu 1151, 면적 및 선분 수 + 이산 화 + 스캐닝)

/*http://poj.org/problem?id=1151
Atlantis
Time Limit: 1000MS  Memory Limit: 10000K
Total Submissions: 14468  Accepted: 5551
Description
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.
Input
The input 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.
Output
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.
Sample Input
2
10 10 20 20
15 15 25 25.5
0
Sample Output
Test case #1
Total explored area: 180.00
Source
Mid-Central European Regional Contest 2000
생각:
직사각형 합 의 면적 을 구하 다.
선분 수 + 이산 화 + 스캐닝 라인
템 플 릿
*/
2011-04-24 13:48
hdu 1542 pku 1151 Atlantis [선분 수 는 직사각형 을 구 합 니 다.]
hdu 1542 pku 1151 Atlantis [선분 수 는 직사각형 을 구 합 니 다.]
[제목]:
선분 수 고전 응용, 직사각형 과 면적 구하 기
[분석]:
첫 번 째 직사각형 기하학 문 제 는 주로 선분 수 를 연습 해서 온 것 이다.
오랫동안 해 왔 는데, 주로 선분 트 리 로 이 문 제 를 어떻게 유지 하 는 지 에 걸 렸 다.
소결 분석 을 썼 다
직사각형 을 구 하 는 것 은 사각형 의 위치 가 다 변 할 수 있 기 때문에 사각형 의 면적 은 단번에 구하 기 어렵다.
이때 '분할' 의 사상 을 채택 할 수 있다. 즉, 전체 덩어리의 사각형 면적 을 몇 개의 작은 사각형 의 면적 으로 분할 한 다음 에 화합 을 구하 면 된다
여기 서 우 리 는 이렇게 해서 모든 사각형 을 투영 할 수 있다. x 좌표 축 올 리 기 y 축 에 도 투영 할 수 있다. x 축 이 올 라 가면 직사각형 이 세로 로 자 르 는 것 과 같다)
그리고 우 리 는 사각형 을 매 거 할 수 있다. x 좌표, 그리고 현재 인접 검출 x 좌표 상 y 방향의 합 법 적 인 길 이 는 두 가지 상승 이 바로 면적 이다.
그리고 그 걸 어떻게 선분 트 리 로 지 키 느 냐 가 관건 이에 요. "합 법 적 인 길이"
이렇게 해도 돼 요.
선분 트 리 의 노드 를 이렇게 정의 합 니 다.
struct node { int left,right,cov; double len; }
cov 현재 노드 구간 이 덮어 쓸 지 여부 입 니 다. len 현재 구간 의 합 법 적 인 길이 입 니 다.
그리고 우 리 는 '스캐닝 라인' 의 방법 을 통 해 스캐닝 을 한다.
매 거 x 의 세로 변, 사각형 의 왼쪽 에 있 는 세로 변 은 바로 입 변 이 고 오른쪽 에 있 는 것 은 바로 나 간 것 이다.
그리고 이 모든 걸 세로 로. x 좌표 증가 정렬, 매번 삽입 작업
좌표 가 반드시 정수 가 아니 기 때문에 이산 화 처리 가 필요 하 다.
삽입 할 때마다 현재 구간 이 완전히 덮어 쓰 이면 맞 아야 합 니 다. cov 도 메 인 업데이트
가장자리 로 들어가다 +1 아웃 사 이 드 -1
업데이트 완료 후 현재 노드 의 cov 도 메 인 크기 0
하면, 만약, 만약... 0, 그러면 현재 노드 의 len 도 메 인 은 노드 가 덮 인 구간 입 니 다.
그렇지 않 으 면
잎 사 귀 노드 라면, len=0
내부 노드 가 있 으 면 아들 len 화합
이상:http://hi.baidu.com/fantasyni/item/b5b6f21b9d9353503b176e05
다음 코드 는 템 플 릿 을 옮 겼 습 니 다:

#include<stdio.h>
#include<iomanip>
#include<cmath>
#include<string.h>
#include<algorithm>
#include <iostream>
using namespace std;
const int maxn=204;
struct node
{
int st,ed,c;//c:     ，m    
  double m;
}tr[maxn*4];
struct Line//      
{
double x,y1,y2;
bool s;//s=1.   ，s=0   
}line[maxn];
double y[maxn],ty[maxn];//        
//     
void build(int root,int st,int ed)
 {tr[root].st=st;
tr[root].ed=ed;
 tr[root].c=0;
tr[root].m=0;
if(ed-st>1)
 {int mid=(st+ed)/2;
 build(root*2,st,mid);
 build(root*2+1,mid,ed);
 }
  }
inline void updata(int root)//    ............
{
 if(tr[root].c>0)//      
 tr[root].m=y[tr[root].ed-1]-y[tr[root].st-1];
 else if(tr[root].ed-tr[root].st==1)
   tr[root].m=0;
else
 tr[root].m=tr[root*2].m+tr[root*2+1].m;
}
void insert(int root,int st,int ed)
{
if(st<=tr[root].st&&tr[root].ed<=ed)
 {
tr[root].c++;
  updata(root);
return;
 }
 if(tr[root].st-tr[root].ed==-1)return;
int mid=(tr[root].st+tr[root].ed)/2;
if(st<mid)insert(root*2,st,ed);
 if(ed>mid)insert(root*2+1,st,ed);
updata(root);
 }
void Delete(int root,int st, int ed)
{
if(st<=tr[root].st&&tr[root].ed<=ed)
 {
tr[root].c--;
  updata(root);
return;
 }
 if(tr[root].st-tr[root].ed==-1)return;
int mid=(tr[root].st+tr[root].ed)/2;
if(st<mid)Delete(root*2,st,ed);
 if(ed>mid)Delete(root*2+1,st,ed);
updata(root);
}
int Correspond(int n,double t )//       t, y[]        
{int low,high,mid;
  low=0;
high=n-1;
while(low<high)
 {
 mid=(low+high)/2;
if(t>y[mid])
 low=mid+1;
else
 high=mid;
 }
return high+1;
}
bool cmp(Line l1,Line l2)
{
return l1.x<l2.x;
}
int main()
{
int n,i,num,l,r,c=0;
 double area,x1,x2,y1,y2;
while(scanf("%d",&n)!=EOF&&n!=0)
 {
  for(i=0;i<n;i++)
  {
  scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
 line[2*i].x=x1;line[2*i].y1=y1;
 line[2*i].y2=y2;line[2*i].s=1;
line[2*i+1].x=x2;line[2*i+1].y1=y1;
 line[2*i+1].y2=y2;line[2*i+1].s=0;
 ty[2*i]=y1;
ty[2*i+1]=y2;
  }
 n=n*2;
 sort(line,line+n,cmp);//       
 sort(ty,ty+n);//        
 y[0]=ty[0];
for(i=num=1;i<n;i++)//       
  {if(ty[i]!=ty[i-1])
   {y[num++]=ty[i];}
  }
 build(1,1,num);//             
  area=0;
//for(i=0;i<num;i++)
 // printf("%.2lf
",y[i]);
for(i=0;i<n-1;i++)
  {
  l=Correspond(num,line[i].y1);//       y[]     
   r=Correspond(num,line[i].y2);
 if(line[i].s)
insert(1, l, r);
 else //       
 Delete(1, l, r);
 area += tr[1].m * (line[i+1].x - line[i].x); }
printf("Test case #%d
",++c);
 printf("Total explored area: %.2lf

",area);
 }
 return 0;
}