# Poj Solution 2574

```http://poj.org/problem?id=2574

#include<iostream>
#include"stdio.h"
#include"math.h"

#include"algorithm"

using namespace std;

//////////////////////////////
#define Type double /*????????*/
//////////////////////////////

struct point
{Type x,y;
point(){x=y=0;}
point(Type &x,Type &y):x(x),y(y){;}
bool operator==(point &a){return x==a.x&&y==a.y;}
};

inline Type cheng(point a,point b,point c)
{return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);}

struct line
{point a,b;
line(){;}
line(point &x,point &y):a(x),b(y)
{;}
};

////////////////////////////////////////////////////////////////

line l[110];
long xmin,ymin,xmax,ymax;
double ly[110];
int n,m;

struct piece
{
double yl,yr;
}pc[110];

void fillpiece(long x)
{
line l1,l2;int i;

m=0;
for(i=0;i<n;i++)
if(l[i].a.x<=x&&x+1<=l[i].b.x)
{
pc[m].yl=l[i].a.y+ly[i]*(x-l[i].a.x);
pc[m].yr=l[i].a.y+ly[i]*(x+1-l[i].a.x);
m++;
}

}

void doit()
{
long x,i,t;double t1,t2;
__int64 s=0;

for( x=xmin; x<xmax; x++ )
{
fillpiece(x);
for( i=0; i<m; i+=2 )
{
t1=pc[i+1].yl<pc[i+1].yr?pc[i+1].yl:pc[i+1].yr;
t2=pc[i].yl>pc[i].yr?pc[i].yl:pc[i].yr;

t=(long)t1-(long)(t2+0.999999);
if(t>0)s+=t;
}
}

printf("%I64dn",s);
return ;
}

int cmp1(line l1,line l2)
{
double min = l1.a.x > l2.a.x ? l1.a.x : l2.a.x ,
max = l1.b.x < l2.b.x ? l1.b.x : l2.b.x ,
c = ( min + max ) / 2 ;

return max > min && l1.a.y+(l1.b.y-l1.a.y)/(l1.b.x-l1.a.x)*(c-l1.a.x) <
l2.a.y+(l2.b.y-l2.a.y)/(l2.b.x-l2.a.x)*(c-l2.a.x) ;
}

void init()
{
xmin=2000000;ymin=2000000;ymax=-2000000;xmax=-2000000;

int i,j;point a,b;

for( n=0; scanf( "%lf %lf", &a.x, &a.y ) == 2 ; n++ )
{
xmax=xmax>a.x?xmax:a.x;
xmin=xmin<a.x?xmin:a.x;
ymax=ymax>a.y?ymax:a.y;
ymin=ymin<a.y?ymin:a.y;

if(n)
{
l[n].a=a;l[n].b=b;
}
b=a;
}

l[0].a=l[1].b;l[0].b=b;

for(i=0;i<n;i++)
{
if(l[i].a.x>l[i].b.x)
swap(l[i].a,l[i].b);
}

for( i=0;i<n; )
{
bool key;
for( i=0,key=true; i<n&&key; i++ )
for( j=i+1; j<n; j++ )
if( cmp1( l[j], l[i] ) )
{
swap( l[j], l[i] );
key = false;
break;
}
}

for(i=0;i<n;i++)
{
ly[i]=(double)(l[i].b.y-l[i].a.y)/(l[i].b.x-l[i].a.x);
}
ymin--;
ymax++;
}

int main()
{
init();
doit();
return 0;
}

```
This entry was posted in poj. Bookmark the permalink.