程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 1177 Picture(掃描線求周長)

POJ 1177 Picture(掃描線求周長)

編輯：C++入門知識

POJ 1177 Picture(掃描線求周長)

與求面積並的差不多，但是這個與掃描的方向相同的情況不太好處理，如果掃描線離散化兩次掃兩遍其實也可以解決這個問題，但是這樣無論在時間還是空間上稍微就有點浪費了啊。這裡因為我是離散x坐標的所以對於平行於y軸的方向上的統計比較難統計。處理的方法是：標記區間左邊的斷點，和右邊的斷點，求出這個區間一共有多少個斷點。就可以統計出平行於y軸的長度了。這裡合並的時候需要判斷右邊的左區間和左邊的右區間是否相同，如果相同的話，說明他們連接到了一起，要減去多加的。

Picture Time Limit: 2000MS Memory Limit: 10000K Total Submissions: 10300 Accepted: 5462

Description

A number of rectangular posters, photographs and other pictures of the same shape are pasted on a wall. Their sides are all vertical or horizontal. Each rectangle can be partially or totally covered by the others. The length of the boundary of the union of all rectangles is called the perimeter.

Write a program to calculate the perimeter. An example with 7 rectangles is shown in Figure 1.

The cZ喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcnJlc3BvbmRpbmcgYm91bmRhcnkgaXMgdGhlIHdob2xlIHNldCBvZiBsaW5lIHNlZ21lbnRzIGRyYXduIGluIEZpZ3VyZSAyLiA8YnI+CjxjZW50ZXI+PGltZyBzcmM9"http://www.2cto.com/uploadfile/Collfiles/20140809/20140809090654208.jpg" alt="\">
The vertices of all rectangles have integer coordinates.

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 lines, one can find the integer coordinates of the lower left vertex and the upper right vertex of each rectangle. The values of those coordinates are given as ordered pairs consisting of an x-coordinate followed by a y-coordinate.

0 <= number of rectangles < 5000
All coordinates are in the range [-10000,10000] and any existing rectangle has a positive area.

Output

Your program is to write to standard output. The output must contain a single line with a non-negative integer which corresponds 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

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define eps 1e-12
///#define M 1000100
#define LL __int64
///#define LL long long
///#define INF 0x7ffffff
#define INF 0x3f3f3f3f
#define PI 3.1415926535898
#define zero(x) ((fabs(x)>1;
        if(a[mid] == x) return mid;
        else if(a[mid] < x) l = mid+1;
        else r = mid-1;
    }
    return -1;
}

void Up(int l, int r, int site)
{
    if(cnt[site])
    {
        sum[site] = dc[r+1]-dc[l];
        Left[site] = Right[site] = 1;
        ans[site] = 2;
    }
    else if(l == r)
    {
        sum[site] = 0;
        ans[site] = 0;
        Left[site] = Right[site] = 0;
    }
    else
    {
        sum[site] = sum[site<<1]+sum[site<<1|1];
        ans[site] = ans[site<<1]+ans[site<<1|1];
        Left[site] = Left[site<<1];
        Right[site] = Right[site<<1|1];
        if(Left[site<<1|1] && Right[site<<1]) ans[site] -= 2;
    }
}


void Update(int l, int r, int L, int R, int d, int site)
{
    if(L <= l && r <= R)
    {
        cnt[site] += d;
        Up(l, r, site);
        return;
    }
    int mid = (l+r)>>1;
    if(L <= mid) Update(l, mid, L, R, d, site<<1);
    if(R > mid) Update(mid+1, r, L, R, d, site<<1|1);
    Up(l, r, site);
}
int main()
{
    int n;
    while(cin >>n)
    {
        if(!n) break;
        int x1, y1, x2, y2;
        int m = 0;
        for(int i = 0; i < n; i++)
        {
            scanf("%d %d %d %d",&x1, &y1, &x2, &y2);
            dc[m] = x1;
            f[m].l = x1;
            f[m].r = x2;
            f[m].h = y1;
            f[m++].x = 1;

            dc[m] = x2;
            f[m].l = x1;
            f[m].r = x2;
            f[m].h = y2;
            f[m++].x = -1;
        }
        sort(dc, dc+m);
        sort(f, f+m, cmp);
        int k = unique(dc, dc+m)-dc;
        memset(cnt, 0, sizeof(cnt));
        memset(sum, 0, sizeof(sum));
        memset(ans, 0, sizeof(ans));
        memset(Left, 0, sizeof(Left));
        memset(Right, 0, sizeof(Right));
        int res = 0;
        int x = 0;
        for(int i = 0; i < m; i++)
        {
            int l = Find(f[i].l, dc, k);
            int r = Find(f[i].r, dc, k)-1;
            if(l <= r) Update(0, k-1, l, r, f[i].x, 1);
            if(i+1 < m) res += ans[1]*(f[i+1].h-f[i].h);
            res += abs(sum[1]-x);
            x = sum[1];
        }
        cout<