선분 트 리 - 스캐닝 라인

There are nnn rectangles on the plane. The problem is to find the area of the union of these rectangles. Note that these rectangles might overlap with each other, and the overlapped areas of these rectangles shall not be counted more than once. For example, given a rectangleAAA with the bottom left corner located at (0,0)(0, 0)(0,0) and the top right corner at (2,2)(2, 2)(2,2), and the other rectangle BBB with the bottom left corner located at (1,1)(1,1)(1,1) and the top right corner at (3,3)(3,3)(3,3), it follows that the area of the union of AAA and BBB should be 777, instead of 888.
Although the problem looks simple at the first glance, it might take a while to figure out how to do it correctly. Note that the shape of the union can be very complicated, and the intersected areas can be overlapped by more than two rectangles.
Note:
(1) The coordinates of these rectangles are given in integers. So you do not have to worry about the floating point round-off errors. However, these integers can be as large as1,000,0001,000,0001,000,000.
(2) To make the problem easier, you do not have to worry about the sum of the areas exceeding the long integer precision. That is, you can assume that the total area does not result in integer overflow.
Input Format
Several sets of rectangles configurations. The inputs are a list of integers. Within each set, the first integer (in a single line) represents the number of rectangles, n, which can be as large as100010001000. After n, there will be n lines representing the n rectangles; each line contains four integers , which means that the bottom left corner of the rectangle is located at (a,b)(a, b)(a,b), and the top right corner of the rectangle is located at (c,d)(c, d)(c,d). Note that integers aaa,bbb,ccc,ddd can be as large as 1,000,0001,000,0001,000,000.
These configurations of rectangles occur repetitively in the input as the pattern described above. An integern=0n = 0n=0 (zero) signifies the end of input.
Output Format
For each set of the rectangles configurations appeared in the input, calculate the total area of the union of the rectangles. Again, these rectangles might overlap each other, and the intersecting areas of these rectangles can only be counted once. Output a single star '*' to signify the end of outputs.
샘플 입력

샘플 출력

7
3
*

Code:

#include 
#include 
#include 
#include 
using namespace std;
const int AX = 1e4+6;
struct Node
{ 
    double l , r , y; 
    int cover;
    Node(){};
    Node(double l_ , double r_ , double y_ , int cover_ ){
        l = l_ ; r = r_ ; y = y_ ; cover = cover_;
    }
    bool operator > 1;
        if( X[mid] == key ) return mid;
        else if( X[mid] < key ) l = mid + 1;
        else r = mid - 1;
    }
}

void push_up(int root, int l, int r)
{
    if( falg[root] ) sum[root] = X[r+1] - X[l] ;
    else if(l == r) sum[root]=0 ;
    else sum[root] = sum[root*2] + sum[root*2+1] ;
}
void update(int root , int l , int r , int L , int R , int cover){
    if( L <= l && R >= r ){
        falg[root] += cover;
        push_up(root,l,r);
        return ;
    }
    int mid = ( l + r ) >> 1;
    if( R <= mid ) update(root*2,l,mid,L,R,cover);
    else if(L > mid) update(root*2+1,mid+1,r,L,R,cover);
    else{
        update(root*2,l,mid,L,mid,cover);
        update(root*2+1,mid+1,r,mid+1,R,cover);
    }
    push_up(root,l,r);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n;
    int Case = 0;
    while( cin >> n && n ){
        memset(falg,0,sizeof(falg));
        memset(sum,0,sizeof(sum));
        int num = 0;
        for( int i = 0 ; i < n ; i++ ){
            double x1 , y1 , x2 ,y2 ;
            cin >> x1 >> y1 >> x2 >> y2;
            line[++num] = Node(x1,x2,y1,1);
            X[num] = x1;
            line[++num] = Node(x1,x2,y2,-1);
            X[num] = x2;
        }
        sort(X+1,X+1+num);
        sort(line+1,line+1+num);
        int cnt = 1;
        for( int i = 2 ; i <= num ; i++ ){
            if( X[i] != X[i+1] ){
                X[++cnt] = X[i];
            }
        }
        int res = 0;
        for( int i = 1 ; i < num ; i++ ){
            int l = binary_search(line[i].l,cnt);
            int r = binary_search(line[i].r,cnt)-1;
            update(1,1,cnt,l,r,line[i].cover);
            res += sum[1] * (line[i+1].y - line[i].y);
        }
        cout << res << endl;
    }
    cout << '*' << endl;
    return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

HDU - 1166 - 적병 포진 (나무형 수조 또는 선분 수)

C 국 의 앙 숙 A 국 은 그동안 군사훈련 을 하고 있 었 기 때문에 C 국 간첩 두목 인 데 릭 과 그의 수하 인 티 디 는 또 바 빠 지기 시작 했다.A 국 가 는 해안선 을 따라 직선 으로 N 개 공병 캠프 ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

선분 트 리 - 스캐닝 라인

좋은 웹페이지 즐겨찾기