[POJ 1177] | Eurce's Blog

题意大概是，给出N个矩形的描述，矩形间可能有重叠，问最后图形的总周长。

这题和早上做的November Rain都被人分类成线段树，但我愣是没有想明白，这个线段树可以怎么用。也都是数组处理了一下就A了。

说说这题，首先周长可以划分为平行于x轴和平行与y轴两部分。这两部分是独立的，可以分类处理，且处理方式类似。下面以与x轴平行为例说明。

首先将所有点坐标离散化，然后用一个struct数组，记录每条边的：y坐标、起止x离散坐标、下边界标记b（是某矩形下边界则为1，否则为0）。然后将2N条边先按y从小到大，再按x从小到大排序。初始化一个全0的数组t，大小为离散化x坐标的个数，表示某段边被覆盖的次数。然后遍历struct数组，对每条边，更新其包含的各线段j的覆盖情况，若边的b==1，则t[j]++，若此时t[j]==1则表示为图形的下边界，为周长的一部分；若边的b==0，则t[j]–，若此时t[j]==0则表示为图形的上边界，也为周长的一部分。

与Y轴平行的边，处理方式类似。由此便能在O(2N*lg(2N)+2NK)的时间内计算完整个图形的周长了，这里K是每条边包含离散线段的数目。貌似K最多是O(N)的，但题目没有这么刁钻的数据，最后也就跑了16MS。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int n,r[5000][4],ei[20001],er[10000],d[10000],erl,pl,sum;
int t[20001],tl;

struct P
{
    int f,es,ed;
    char b;
    bool operator < (const P &p) const
    {
        if(f<p.f) return 1;
        if(f>p.f) return 0;
        return es<p.es;
    }
}p[10000];

void init()
{
    int i;
    for(i=0;i<n;i++)
    {
        scanf("%d%d%d%d",&r[i][0],&r[i][1],&r[i][2],&r[i][3]);
        r[i][0]+=10000; r[i][1]+=10000;
        r[i][2]+=10000; r[i][3]+=10000;
    }
    sum=0;
}

void solve()
{
    int i,j,k,l;
    for(i=tl=0;i<n;i++)
    {
        t[tl++]=r[i][0]; t[tl++]=r[i][2];
    }
    sort(t,t+tl);
    ei[t[0]]=0;
    er[0]=t[0];
    for(i=erl=1;i<tl;i++)
    {
        if(t[i]==t[i-1])
            continue;
        ei[t[i]]=erl;
        er[erl]=t[i];
        d[erl]=er[erl]-er[erl-1];
        erl++;
    }
    for(i=pl=0;i<n;i++)
    {
        p[pl].f=r[i][1]; p[pl].es=ei[r[i][0]];
        p[pl].ed=ei[r[i][2]]; p[pl].b=1; pl++;
        p[pl].f=r[i][3]; p[pl].es=ei[r[i][0]];
        p[pl].ed=ei[r[i][2]]; p[pl].b=0; pl++;
    }
    sort(p,p+pl);
    memset(t,0,sizeof t);
    for(i=0;i<pl;i++)
    {
        if(p[i].b)
        {
            for(j=p[i].es+1;j<=p[i].ed;j++)
            {
                t[j]++;
                if(t[j]==1)
                    sum+=d[j];
            }
        }
        else
        {
            for(j=p[i].es+1;j<=p[i].ed;j++)
            {
                t[j]--;
                if(t[j]==0)
                    sum+=d[j];
            }
        }
    }
    for(i=tl=0;i<n;i++)
    {
        t[tl++]=r[i][1]; t[tl++]=r[i][3];
    }
    sort(t,t+tl);
    ei[t[0]]=0;
    er[0]=t[0];
    for(i=erl=1;i<tl;i++)
    {
        if(t[i]==t[i-1])
            continue;
        ei[t[i]]=erl;
        er[erl]=t[i];
        d[erl]=er[erl]-er[erl-1];
        erl++;
    }
    for(i=pl=0;i<n;i++)
    {
        p[pl].f=r[i][0]; p[pl].es=ei[r[i][1]];
        p[pl].ed=ei[r[i][3]]; p[pl].b=1; pl++;
        p[pl].f=r[i][2]; p[pl].es=ei[r[i][1]];
        p[pl].ed=ei[r[i][3]]; p[pl].b=0; pl++;
    }
    sort(p,p+pl);
    memset(t,0,sizeof t);
    for(i=0;i<pl;i++)
    {
        if(p[i].b)
        {
            for(j=p[i].es+1;j<=p[i].ed;j++)
            {
                t[j]++;
                if(t[j]==1)
                    sum+=d[j];
            }
        }
        else
        {
            for(j=p[i].es+1;j<=p[i].ed;j++)
            {
                t[j]--;
                if(t[j]==0)
                    sum+=d[j];
            }
        }
    }
    printf("%d\n",sum);
}

int main()
{
    while(~scanf("%d",&n))
    {
        init();
        solve();
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int n,r[5000][4],ei[20001],er[10000],d[10000],erl,pl,sum;

int t[20001],tl;

struct P

{

int f,es,ed;

char b;

bool operator < (const P &p) const

{

if(f<p.f) return 1;

if(f>p.f) return 0;

return es<p.es;

}

}p[10000];

void init()

{

int i;

for(i=0;i<n;i++)

{

scanf("%d%d%d%d",&r[i][0],&r[i][1],&r[i][2],&r[i][3]);

r[i][0]+=10000; r[i][1]+=10000;

r[i][2]+=10000; r[i][3]+=10000;

}

sum=0;

}

void solve()

{

int i,j,k,l;

for(i=tl=0;i<n;i++)

{

t[tl++]=r[i][0]; t[tl++]=r[i][2];

}

sort(t,t+tl);

ei[t[0]]=0;

er[0]=t[0];

for(i=erl=1;i<tl;i++)

{

if(t[i]==t[i-1])

continue;

ei[t[i]]=erl;

er[erl]=t[i];

d[erl]=er[erl]-er[erl-1];

erl++;

}

for(i=pl=0;i<n;i++)

{

p[pl].f=r[i][1]; p[pl].es=ei[r[i][0]];

p[pl].ed=ei[r[i][2]]; p[pl].b=1; pl++;

p[pl].f=r[i][3]; p[pl].es=ei[r[i][0]];

p[pl].ed=ei[r[i][2]]; p[pl].b=0; pl++;

}

sort(p,p+pl);

memset(t,0,sizeof t);

for(i=0;i<pl;i++)

{

if(p[i].b)

{

for(j=p[i].es+1;j<=p[i].ed;j++)

{

t[j]++;

if(t[j]==1)

sum+=d[j];

}

else

{

for(j=p[i].es+1;j<=p[i].ed;j++)

{

t[j]--;

if(t[j]==0)

sum+=d[j];

}

for(i=tl=0;i<n;i++)

{

t[tl++]=r[i][1]; t[tl++]=r[i][3];

}

sort(t,t+tl);

ei[t[0]]=0;

er[0]=t[0];

for(i=erl=1;i<tl;i++)

{

if(t[i]==t[i-1])

continue;

ei[t[i]]=erl;

er[erl]=t[i];

d[erl]=er[erl]-er[erl-1];

erl++;

}

for(i=pl=0;i<n;i++)

{

p[pl].f=r[i][0]; p[pl].es=ei[r[i][1]];

p[pl].ed=ei[r[i][3]]; p[pl].b=1; pl++;

p[pl].f=r[i][2]; p[pl].es=ei[r[i][1]];

p[pl].ed=ei[r[i][3]]; p[pl].b=0; pl++;

}

sort(p,p+pl);

memset(t,0,sizeof t);

for(i=0;i<pl;i++)

{

if(p[i].b)

{

for(j=p[i].es+1;j<=p[i].ed;j++)

{

t[j]++;

if(t[j]==1)

sum+=d[j];

}

else

{

for(j=p[i].es+1;j<=p[i].ed;j++)

{

t[j]--;

if(t[j]==0)

sum+=d[j];

}

printf("%d\n",sum);

}

int main()

{

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

{

init();

solve();

}

return 0;

}