1. 首页
2. 扫描线
3. 本页

HDU 1542 Atlantis (扫描线)

题目链接：点我~~

题意：还未更新。。。

思路：还未更新。。。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PI;
typedef pair< PI, int> PII;
const double eps=1e-5;
const double pi=acos(-1.0);
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
#define Key_value ch[ch[root][1]][0]
const int MAXN = 100000+100;
const int MAXM = 10100;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1

double sum[MAXN<<2];
double a[MAXN];
int mk[MAXN<<2];

struct Seg
{
    double l,r,h;
    int f;
    Seg() {};
    Seg(double _l,double _r,double _h,int _f):l(_l),r(_r),h(_h),f(_f) {};
    bool operator <(const Seg &b)const
    {
        return h<b.h;
    }
} seg[MAXN];

inline void pushup(int rt,int l,int r)
{
    if(mk[rt])
        sum[rt]=a[r+1]-a[l];
    else if(l==r)
        sum[rt]=0;
    else
        sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}

void modify(int L,int R,int add,int l,int r,int rt)
{
    if(L<=l && r<=R)
    {
        mk[rt]+=add;
        pushup(rt,l,r);
        return ;
    }
    int mid=(l+r)>>1;
    if(L<=mid)
        modify(L,R,add,lson);
    if(R>mid)
        modify(L,R,add,rson);
    pushup(rt,l,r);
}

int main()
{
    int n;
    int casee=1;
    while(~scanf("%d",&n),n)
    {
        double x1,y1,x2,y2;
        int cnt=0;
        for(int i=0; i<n; ++i)
        {
            cin>>x1>>y1>>x2>>y2;
            a[cnt]=x1;
            seg[cnt++]=Seg(x1,x2,y1,1);
            a[cnt]=x2;
            seg[cnt++]=Seg(x1,x2,y2,-1);
        }
        sort(a,a+cnt);
        sort(seg,seg+cnt);
        int k=unique(a,a+cnt)-a;
        double ans=0;
        memset(sum,0,sizeof sum);
        memset(mk,0,sizeof mk);
        for(int i=0; i<cnt-1; ++i)
        {
            int l=lower_bound(a,a+k,seg[i].l)-a;
            int r=lower_bound(a,a+k,seg[i].r)-a-1;
                modify(l,r,seg[i].f,0,k-1,1);
            ans+=sum[1]*(seg[i+1].h-seg[i].h);
        }
        printf("Test case #%d\n",casee++);
        printf("Total explored area: %.2lf\n\n",ans);
    }

    return 0;
}