首页 > 代码库 > HNU12884_Area Coverage(扫描线/线段树+离散化)

HNU12884_Area Coverage(扫描线/线段树+离散化)

2024-07-18 00:37:22   221人阅读

解题报告

题目传送门

题意：

又是求面积并

思路：

又是求面积并，还被坑了，题目明明描述的是int坐标，用了double才过。。。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
struct Seg {
    double lx,rx,h;
    int v;
    friend bool operator <(Seg a,Seg b) {
        return a.h<b.h;
    }
} seg[2100];
double _hash[4100],sum[201000];
int lz[201000];
void push_up(int rt,int l,int r) {
    if(lz[rt])sum[rt]=_hash[r+1]-_hash[l];
    else if(l==r)sum[rt]=0;
    else sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void update(int rt,int l,int r,int ql,int qr,int v) {
    if(ql>r||qr<l)return ;
    if(ql<=l&&r<=qr) {
        lz[rt]+=v;
        push_up(rt,l,r);
        return ;
    }
    int mid=(l+r)>>1;
    update(rt<<1,l,mid,ql,qr,v);
    update(rt<<1|1,mid+1,r,ql,qr,v);
    push_up(rt,l,r);
}
int main() {
    int t,n,i,j;
    double x1,x2,y1,y2;
    scanf("%d",&t);
    while(t--) {
        memset(sum,0,sizeof(sum));
        memset(_hash,0,sizeof(_hash));
        memset(lz,0,sizeof(lz));
        scanf("%d",&n);
        for(i=0; i<n; i++) {
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            _hash[i]=x1,_hash[i+n]=x2;
            seg[i].lx=x1,seg[i].rx=x2,seg[i].v=1,seg[i].h=y1;
            seg[i+n].lx=x1,seg[i+n].rx=x2,seg[i+n].v=-1,seg[i+n].h=y2;
        }
        sort(_hash,_hash+n*2);
        sort(seg,seg+n*2);
        int m=unique(_hash,_hash+n*2)-_hash;
        double ans=0;
        for(i=0; i<n*2-1; i++) {
            int ql=lower_bound(_hash,_hash+m,seg[i].lx)-_hash;
            int qr=lower_bound(_hash,_hash+m,seg[i].rx)-_hash-1;
            update(1,0,m-1,ql,qr,seg[i].v);
            ans+=sum[1]*(seg[i+1].h-seg[i].h);
        }
        printf("%.0lf\n",ans);
    }
    return 0;
}
Area Coverage
Time Limit: 10000ms, Special Time Limit:2500ms, Memory Limit:65536KB
Total submit users: 22, Accepted users: 16
Problem 12884 : No special judgement
Problem description

In this day and age, a lot of the spying on other countries is done with the use of satellites and drones equipped with cameras. All these photographs of various sizes and from various sources can be combined to give a picture of the country as a whole.
Given the photographs (that is to say, the rectangular area covered by each, since the contents of the photographs themselves are of course top-secret!), can you work out what the total area is of all that is photographed? Note that certain areas can appear on multiple photographs and should be counted only once.

Input

On the first line one positive number: the number of test cases, at most 100. After that per test case:
 one line with an integer n (1<=n<=1000): the number of photographs.
 n lines with four space-separated integers x1, y1, x2 and y2 (0<=x1; y1; x2; y2<=1 000 000, x1 < x2 and y1 < y2): the coordinates of the southwest and northeast corner, respectively, of each photograph. The photographs are all rectangular in shape with their other corners at (x1; y2) and (x2; y1).
The coordinates correspond to a flat two-dimensional space (i.e. we assume the Earth to be flat).

Output

Per test case:
 one line with an integer: the total area of all that appears on the photographs.

Sample Input
2
3
0 6 20 16
14 0 24 10
50 50 60 60
2
0 0 20 10
10 4 14 8
Sample Output
376
200
Problem Source
BAPC preliminary 2013


联系
我们