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;
}