POJ 1177_Picture

Picture
Time Limit: 2000 MS
 
メモリLimit: 100000 K
Total Submissions: 11643
 
Acceepted: 6141
幾何学、走査線を計算して、何日間見て少し分かります.
おすすめブログ:http://www.cppblog.com/abilitytao/archive/2010/07/21/120927.html
http://www.cnblogs.com/shuaiwhu/archive/2012/04/22/2464876.html
Description
A number of rectanglar posters、photographs and other pictures of the same shpe are pasted on a wall.The ir sides are all verticantal.Each rectanle can be partially or totally covered bythe the herectry of 
Write a program to calculate the perimeter.An example with 7 rectangles is shown in Figure 1. 

The cores ponding boundary is the whole set of line segments drawn in Figre 2. 

The vertices of all rectangles have integer coordination. 
Input
Your program is to read from standard input.The first line contains the number of rectangles pasted on the wall.In each of the subsequent line,one can find the integer coordinates of the lower left vertex and the up per right vertex of each rectanle.The values of those coordination are given as orded pairs consisting of an x-coordinate foordinate.a.ordiordination. 
0<=number of rectangles<5000 
All coordinates are in the range[-10000,000]and any existing rectangle has a positive ara.
Output
Your program is to write to standard output.The out put must contain a single line with a non-negative integer which coreress ponds to the perimeter for the input rectangles.
Sample Input

7
-15 0 5 10
-5 8 20 25
15 -4 24 14
0 -6 16 4
2 15 10 22
30 10 36 20
34 0 40 16

Sample Output

228

ソurce
IOI 1998

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int N=1e4+6;
struct node
{
    int l,r;
    int cover;
    int lcover,rcover;
    int sum;
    int len;
    int seg;

};
node ST[N<<2];
int A[N];
int n,cnt;
struct Line
{
    int x,y1,y2;
    int Inline;
    bool operator1)
    {
        int mid=(l+r)>>1;
        build(l,mid,rt<<1);
        build(mid,r,rt<<1|1);
    }
}
void getsum(int rt)
{
    if(ST[rt].cover>0)
        ST[rt].sum=ST[rt].len;
    else if(ST[rt].r-ST[rt].l>1)
        ST[rt].sum=ST[rt<<1].sum+ST[rt<<1|1].sum;
    else
        ST[rt].sum=0;
}
void getseg(int rt)
{
    if(ST[rt].cover>0)
    {
        ST[rt].lcover=ST[rt].rcover=1;
        ST[rt].seg=1;
    }
    else if(ST[rt].r-ST[rt].l>1)
    {
        ST[rt].lcover=ST[rt<<1].lcover;
        ST[rt].rcover=ST[rt<<1|1].rcover;
        ST[rt].seg=ST[rt<<1].seg+ST[rt<<1|1].seg-ST[rt<<1].rcover*ST[rt<<1|1].lcover;
    }
    else
    {
        ST[rt].rcover=ST[rt].lcover=0;
        ST[rt].seg=0;
    }
}
void Insert(int l,int r,int rt)
{
    if(l==ST[rt].l&&r==ST[rt].r)
        ST[rt].cover++;
    else
    {
        int mid=(ST[rt].l+ST[rt].r)>>1;
        if(l>=mid)
            Insert(l,r,rt<<1|1);
        else if(r<=mid)
            Insert(l,r,rt<<1);
        else
        {
            Insert(l,mid,rt<<1);
            Insert(mid,r,rt<<1|1);
        }
    }
    getsum(rt);
    getseg(rt);
}
void Delete(int l,int r,int rt)
{
    if(l==ST[rt].l&&r==ST[rt].r)
        ST[rt].cover--;
    else
    {
        int mid=(ST[rt].l+ST[rt].r)>>1;
        if(l>=mid)
            Delete(l,r,rt<<1|1);
        else if(r<=mid)
            Delete(l,r,rt<<1);
        else
        {
          Delete(l,mid,rt<<1);
        Delete(mid,r,rt<<1|1);
        }
    }
    getsum(rt);
    getseg(rt);
}
int getx(int x)
{
    return lower_bound(A,A+cnt,x)-A;
}
int main()
{
    while(cin>>n)
    {
        cnt=0;
        int x1,x2,y1,y2;
        for(int i=0;i