poj 1389 Area of Simple Polygons 线段树扫面线，和1151一样的嘛

这道题和1151一样嘛！自己有打一边温习温习

详细讲解看

http://blog.csdn.net/youngyangyang04/article/details/7787693

#include<iostream>#include<stdio.h>#include<algorithm>using namespace std;#define N 1005struct ode{    int y1,y2,x,flag;}node[N*3];bool cmp(ode a,ode b){    return a.x<b.x;}int y[N*2],pa[N*2];struct Node{    int l;int r;int s;int ml,mr,len;}a[N*6];void build(int i,int left,int right){    a[i].l=left;    a[i].r=right;    a[i].len=0;    a[i].s=0;a[i].mr=y[a[i].r];a[i].ml=y[a[i].l];    if(a[i].r==a[i].l+1) return ;    int mid=(left+right)>>1;    build(i*2,left,mid);    build(i*2+1,mid,right);}int len(int i){    if(a[i].s>0){        return a[i].mr-a[i].ml;    }else if(a[i].r==a[i].l+1){        return 0;    }else{        return a[i*2].len+a[i*2+1].len;    }}void insert(int i,ode m){    if(pa[a[i].l]==m.y1&&pa[a[i].r]==m.y2){        a[i].s+=m.flag;        a[i].len=len(i);        return ;    }    if(m.y2<=pa[a[i*2].r]) insert(i*2,m);    else if(m.y1>=pa[a[i*2+1].l]) insert(i*2+1,m);    else{        ode temp=m;        temp.y2=pa[a[i*2].r];        insert(i*2,temp);        temp=m;        temp.y1=pa[a[i*2+1].l];        insert(i*2+1,temp);    }    a[i].len=len(i);}int main(){//    freopen("in.txt","r",stdin);    int x1,y1,x2,y2;    int t=1;    while(~scanf("%d%d%d%d",&x1,&y1,&x2,&y2)){        if(x1==-1&&x2==-1&&y1==-1&&y2==-1){//            cout<<t<<endl;            if(t==1) continue;            sort(y+1,y+t);            for(int i=1;i<t;i++)                pa[i]=y[i];            sort(node+1,node+t,cmp);            build(1,1,t-1);            insert(1,node[1]);            int sum=0;            for(int i=2;i<t;i++){                sum+=(node[i].x-node[i-1].x)*a[1].len;                insert(1,node[i]);            }            printf("%d\n",sum);            t=1;            continue;        }        node[t].y1=y1;        node[t].y2=y2;        node[t].x=x1;        node[t].flag=1;        y[t++]=y1;        node[t].y1=y1;        node[t].y2=y2;        node[t].x=x2;        node[t].flag=-1;        y[t++]=y2;    }}