[POJ 2043] | Eurce's Blog

计算几何。

题意是，给出一个多边形的顶点（坐标都为整数）描述，要求该多边形在网格上覆盖的格子数目。

基本思路是扫描线，从左到右，同时维护一个有序数组s，记录当前区间内存在的线段的y值，线段必定是成对出现的，且每对线段间的区域为多边形内部。这样就可以计算每个区间内被覆盖的格子数了。

具体的实现上，首先初始化所有的n条线段，并放入一个表头大小为4001的邻接表中，方便扫描线时将新扫到的线段加入。垂直的线段直接忽略。对线段结构体记录其当前y值，斜率k，终点xr，以及删除标记b。每次处理一个区间的线段时，删除线段即为将标记位置1。对s内的线段排序时，首先将被删除的线段都放到最后，然后若y值不同则按y从小到大排序，否则再按斜率k从小到大排序。

计算每段区间[x,x+1]内被覆盖的格子数时，需要注意若连续的多条线段过于接近，要避免重复计算。同时取floor或ceil时，需要对y值增或减eps，以舍去计算误差。

总体上来说虽然细节较多，仔细思考后还是比较顺利地1A了。不过也写了一整个下午……

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

#define eps 1e-8

int n,hd[4001],el,ans,sl;
int x[100],y[100],mnx,mxx;

struct E
{
    double y,k;
    int b,xr,p;
}e[100],s[100];

struct CP
{
    bool operator () (const E &p,const E &q) const
    {
        if(p.b>q.b) return 0;
        if(p.b<q.b) return 1;
        if(abs(p.y-q.y)>eps)
            return p.y<q.y;
        else
            return p.k<q.k;
    }
};

inline void adde(int x0,int y0,int x1,int y1)
{
    if(x0==x1) return;
    if(x0>x1)
    {
        x0^=x1^=x0^=x1;
        y0^=y1^=y0^=y1;
    }
    e[el].y=y0;
    e[el].k=1.0*(y1-y0)/(x1-x0);
    e[el].b=0;
    e[el].xr=x1;
    e[el].p=hd[x0];
    hd[x0]=el++;
}

void init()
{
    int i,j,k,l;
    el=sl=ans=0;
    mnx=4001;
    mxx=0;
    memset(hd,-1,sizeof hd);
    for(i=0;i<n;i++)
    {
        scanf("%d%d",&x[i],&y[i]);
        x[i]+=2000;
        y[i]+=2000;
        mxx=max(mxx,x[i]);
        mnx=min(mnx,x[i]);
    }
    adde(x[n-1],y[n-1],x[0],y[0]);
    for(i=0;i<n-1;i++)
        adde(x[i],y[i],x[i+1],y[i+1]);
}

void solve()
{
    int i,j,k,l;
    double yb,yt;
    E *p,*q;
    for(i=mnx;i<mxx;i++)
    {
        k=ans;
        for(l=0;l<sl&&!s[l].b;l++)
        {
            if(s[l].xr==i)
                s[l].b=1;
        }
        for(l=hd[i];l!=-1;l=e[l].p)
            s[sl++]=e[l];
        sort(s,s+sl,CP());
        if(s[0].b)
            continue;
        yt=-1e30;
        for(l=0;l<sl&&!s[l].b;l+=2)
        {
            p=&s[l];
            q=&s[l+1];
            yb=min(floor(p->y+eps),floor(p->y+p->k+eps));
            if(yb<yt)
                yb=yt;
            yt=max(ceil(q->y-eps),ceil(q->y+q->k-eps));
            p->y+=p->k;
            q->y+=q->k;
            ans+=yt-yb;
        }
    }
    printf("%d\n",ans);
}

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

100

101

102

103

104

105

106

107

108

109

110

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

#define eps 1e-8

int n,hd[4001],el,ans,sl;

int x[100],y[100],mnx,mxx;

struct E

{

double y,k;

int b,xr,p;

}e[100],s[100];

struct CP

{

bool operator () (const E &p,const E &q) const

{

if(p.b>q.b) return 0;

if(p.b<q.b) return 1;

if(abs(p.y-q.y)>eps)

return p.y<q.y;

else

return p.k<q.k;

}

};

inline void adde(int x0,int y0,int x1,int y1)

{

if(x0==x1) return;

if(x0>x1)

{

x0^=x1^=x0^=x1;

y0^=y1^=y0^=y1;

}

e[el].y=y0;

e[el].k=1.0*(y1-y0)/(x1-x0);

e[el].b=0;

e[el].xr=x1;

e[el].p=hd[x0];

hd[x0]=el++;

}

void init()

{

int i,j,k,l;

el=sl=ans=0;

mnx=4001;

mxx=0;

memset(hd,-1,sizeof hd);

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

{

scanf("%d%d",&x[i],&y[i]);

x[i]+=2000;

y[i]+=2000;

mxx=max(mxx,x[i]);

mnx=min(mnx,x[i]);

}

adde(x[n-1],y[n-1],x[0],y[0]);

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

adde(x[i],y[i],x[i+1],y[i+1]);

}

void solve()

{

int i,j,k,l;

double yb,yt;

E *p,*q;

for(i=mnx;i<mxx;i++)

{

k=ans;

for(l=0;l<sl&&!s[l].b;l++)

{

if(s[l].xr==i)

s[l].b=1;

}

for(l=hd[i];l!=-1;l=e[l].p)

s[sl++]=e[l];

sort(s,s+sl,CP());

if(s[0].b)

continue;

yt=-1e30;

for(l=0;l<sl&&!s[l].b;l+=2)

{

p=&s[l];

q=&s[l+1];

yb=min(floor(p->y+eps),floor(p->y+p->k+eps));

if(yb<yt)

yb=yt;

yt=max(ceil(q->y-eps),ceil(q->y+q->k-eps));

p->y+=p->k;

q->y+=q->k;

ans+=yt-yb;

}

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

}

int main()

{

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

{

init();

solve();

}

return 0;

}