poj1389Area of Simple Polygons(線段樹+線掃描求矩形面積并)

->題目請戳這裡<-

題目大意：略

題目分析：簡單求矩形面積并，不懂的可以看其他幾篇部落格。這題就是拿來練一下1Y率和敲代碼速度。果然小手一抖，把i和j敲反了卡了一下，BS一下自己。。。

詳情請見代碼：

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1005;
int hash[N + N];
struct node
{
    int x,y1,y2,flag;
}line[N + N];
struct nd
{
    int cover,len;
} tree[N<<3];

int cmp(struct node a,struct node b)
{
    return a.x < b.x;
}

int gety(int x,int len)
{
    int l = 1;
    int r = len;
    int mid;
    while(l <= r)
    {
        mid = (l + r)>>1;
        if(hash[mid] == x)
            return mid;
        else
        {
            if(hash[mid] > x)
                r = mid - 1;
            else
                l = mid + 1;
        }
    }
    return -1;
}

void build(int num,int s,int e)
{
    tree[num].cover = tree[num].len = 0;
    if(s == e)
        return;
    int mid = (s + e)>>1;
    build(num<<1,s,mid);
    build(num<<1|1,mid + 1,e);
}

void insert(int num,int s,int e,int l,int r,int add)
{
    if(s == e)
    {
        tree[num].cover += add;
        if(tree[num].cover)
            tree[num].len = hash[e + 1] - hash[s];
        else
            tree[num].len = 0;
        return;
    }
    if(s == l && r == e)
    {
        tree[num].cover += add;
        if(tree[num].cover)
            tree[num].len = hash[e + 1] - hash[s];
        else
            tree[num].len = tree[num<<1].len + tree[num<<1|1].len;
        return;
    }
    int mid = (s + e)>>1;
    if(r <= mid)
        insert(num<<1,s,mid,l,r,add);
    else
    {
        if(l > mid)
            insert(num<<1|1,mid + 1,e,l,r,add);
        else
        {
            insert(num<<1,s,mid,l,mid,add);
            insert(num<<1|1,mid + 1,e,mid + 1,r,add);
        }
    }
    if(tree[num].cover)
        tree[num].len = hash[e + 1] - hash[s];
    else
        tree[num].len = tree[num<<1].len + tree[num<<1|1].len;
}

int main()
{
    int x1,x2,y1,y2,i,j,m,n;
    while(scanf("%d%d%d%d",&x1,&y1,&x2,&y2) != EOF)
    {
        if(x1 == -1 && x2 == -1 && y1 == -1 && y2 == -1)
            break;
        line[1].x = x1;
        line[1].y1 = y1;
        line[1].y2 = y2;
        line[1].flag = 1;
        line[2].x = x2;
        line[2].y1 = y1;
        line[2].y2 = y2;
        line[2].flag = -1;
        hash[1] = y1;
        hash[2] = y2;
        i = 2;
        while(~scanf("%d%d%d%d",&x1,&y1,&x2,&y2))
        {
            if(x1 == -1 && x2 == -1 && y1 == -1 && y2 == -1)
                break;
            line[i + 1].x = x1;
            line[i + 1].y1 = y1;
            line[i + 1].y2 = y2;
            line[i + 1].flag = 1;
            line[i + 2].x = x2;
            line[i + 2].y1 = y1;
            line[i + 2].y2 = y2;
            line[i + 2].flag = -1;
            hash[i + 1] = y1;
            hash[i + 2] = y2;
            i += 2;
        }
        sort(hash + 1,hash + i + 1);
        m = 2;
        for(j = 2;j <= i;j ++)
            if(hash[j] != hash[j - 1])
                hash[m ++] = hash[j];
        m --;
        build(1,1,m);
        int l,r;
        sort(line + 1,line + i + 1,cmp);
        l = gety(line[1].y1,m);
        r = gety(line[1].y2,m) - 1;
        insert(1,1,m,l,r,line[1].flag);
        int ans = 0;
        for(j = 2;j <= i;j ++)
        {
            ans += (line[j].x - line[j - 1].x) * tree[1].len;
            l = gety(line[j].y1,m);
            r = gety(line[j].y2,m) - 1;
            insert(1,1,m,l,r,line[j].flag);
        }
        printf("%d\n",ans);
    }
    return 0;
}
//228K	16MS