poj-1151-Atlantis-线段树求面积并

非常裸的线段树求面积并。

坐标须要离散化一下。

#include<stdio.h>

#include<iostream>

#include<stdlib.h>

#include<string.h>

#include<algorithm>

#include<vector>

#include<math.h>

#include<map>

#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;

#define maxn 11000

#define mem(a,b) (memset(a),b,sizeof(a))

#define lmin 1

#define rmax len

#define lson l,(l+r)/2,rt<<1

#define rson (l+r)/2+1,r,rt<<1|1

#define root lmin,rmax,1

#define now l,r,rt

#define int_now int l,int r,int rt

#define INF 99999999

#define LL long long

#define mod 10007

#define eps 1e-6

#define zero(x) (fabs(x)<eps?

0:x)

map<double,int>mp;

double du[4010];

int len;

struct list

{

    double x1,y1;

    double x2,y2;

}node[maxn];

struct linen

{

    double y1,y2;

    int leap;

    double x;

    friend bool operator <(const linen &a,const linen &b)

    {

        if(zero(a.x-b.x)!=0) return a.x<b.x;

        else return a.leap>b.leap;

    }

}line[maxn*2];

double num[maxn*4*4*2];

int cover[maxn*4*4*2];

void push_up(int_now)

{

    if(cover[rt]==0)

    {

        num[rt]=num[rt<<1]+num[rt<<1|1];

    }

    if(cover[rt]>=1)

    {

        num[rt]=du[r+1]-du[l];

    }

  //  cout<<rt<<" "<<du[l]<<"===="<<du[r+1]<<" "<<cover[rt]<<" "<<num[rt]<<" "<<sum[rt]<<endl;

}

void push_down(int_now)

{

}

void creat(int_now)

{

    memset(cover,0,sizeof(cover));

    memset(num,0,sizeof(num));

}

void updata(int ll,int rr,int x,int_now)

{

    if(ll>r||rr<l)return;

    if(ll<=l&&rr>=r)

    {

       // cout<<l<<" "<<r<<"-"<<du[l]<<" "<<du[r+1]<<" "<<endl;

        cover[rt]+=x;

        push_up(now);

        return;

    }

    updata(ll,rr,x,lson);

    updata(ll,rr,x,rson);

    push_up(now);

}

int main()

{

    int t,n,s;

    int cas=0;

    while(~scanf("%d",&n)&&n)

    {

        cas++;

        s=0;

        for(int i=1;i<=n;i++)

        {

            scanf("%lf%lf%lf%lf",&node[i].x1,&node[i].y1,&node[i].x2,&node[i].y2);

            du[++s]=node[i].x1;

            du[++s]=node[i].y1;

            du[++s]=node[i].x2;

            du[++s]=node[i].y2;

            line[i*2-1].x=node[i].x1;

            line[i*2-1].y1=node[i].y1;

            line[i*2-1].y2=node[i].y2;

            line[i*2-1].leap=1;

            line[i*2].x=node[i].x2;

            line[i*2].y1=node[i].y1;

            line[i*2].y2=node[i].y2;

            line[i*2].leap=-1;

        }

        sort(line+1,line+n*2+1);

        sort(du+1,du+s+1);

        du[0]=-1;

        len =0;

        mp.clear();

        for(int i=1;i<=s;i++)

        {

            if(du[i]!=du[i-1])

            {

                mp[du[i]]=++len;

                du[len]=du[i];

            }

        }

        creat(root);

        double st=0;

        double are=0.0;

        for(int i=1;i<=len;i++)

        {

           // cout<<i<<"----"<<du[i]<<endl;

        }

        len--;

       // cout<<1<<" "<<len<<" "<<1<<" "<<endl;

        for(int i=1;i<=n*2;i++)

        {

            int l,r;

            l=mp[line[i].y1];

            r=mp[line[i].y2];

            if(zero(line[i].x-st)!=0)

            {

                are+=(line[i].x-st)*num[1];

                st=line[i].x;

            }

           // cout<<line[i].x<<" "<<line[i].y1<<" "<<line[i].y2<<" "<<" "<<line[i].leap<<endl;

            updata(l,r-1,line[i].leap,root);

            //cout<<l<<" "<<r<<" "<<are<<endl;

        }

        printf("Test case #%d\n",cas);

        printf("Total explored area: %.2f\n\n",are);

    }

    return 0;

}