挺惡心的。設(shè)置一條豎掃描線從左往右掃，求出和所有線段的交點的y坐標(biāo)，排序，處理每一列符合條件的豎格子。
要注意ceil和floor，有可能會重復(fù)計數(shù)，小心處理。
Code
#include<iostream>
#include<cmath>
#include<algorithm>
const double inf=1e10;
const double eps=1e-8;
using namespace std;
struct PT
{
double x,y;
}p[110];
struct Seg
{
PT s,t;
}a[110];
struct ty
{
double yl,yr;
}yy[110];
int ynum=0;
int n,sum;
double minx,maxx;
bool cmp(ty a,ty b)
{
if(a.yl==b.yl)
return a.yr<b.yr;
else return a.yl<b.yl;
}
int main()
{
int i,j;
while(scanf("%d",&n)!=EOF&&n)
{
minx=inf;maxx=-inf;ynum=0;
for(i=0;i<n;i++)
{
scanf("%lf%lf",&p[i].x,&p[i].y);
if(p[i].x>maxx)
maxx=p[i].x;
if(p[i].x<minx)
minx=p[i].x;
}
for(i=0;i<n;i++)
{
if(p[i].x<p[(i+1)%n].x)
{
a[i].s=p[i];
a[i].t=p[(i+1)%n];
}
else
{
a[i].s=p[(i+1)%n];
a[i].t=p[i];
}
}
sum=0;
double dx;
for(dx=minx;dx+1<=maxx;dx+=1)//掃描
{
ynum=0;
for(i=0;i<n;i++)
{
if(a[i].s.x<=dx&&a[i].t.x>=dx+1)//每一列格子記錄左端和右端的縱坐標(biāo)
{
yy[ynum].yl=a[i].s.y+(a[i].t.y-a[i].s.y)*(dx-a[i].s.x)/(a[i].t.x-a[i].s.x);
yy[ynum++].yr=a[i].s.y+(a[i].t.y-a[i].s.y)*(dx+1-a[i].s.x)/(a[i].t.x-a[i].s.x);
}
}
sort(yy,yy+ynum,cmp);//排序
int tmp=0,pceil=-2100;//pceil代表同一小段x值中，之前一小段的y最大值
for(i=0;i+1<ynum;i+=2)//對每一列累加處理。
{
double t1,t2;
t1=ceil(max(yy[i+1].yr,yy[i+1].yl));
t2=floor(min(yy[i].yr,yy[i].yl));
tmp+=t1-t2;
if(t2<=pceil)
tmp-=(pceil-t2);
pceil=t1;
}
if(tmp>0)
sum+=tmp;
}
printf("%d\n",sum);
}
return 0;
}