Poj Solution 3130

http://poj.org/problem?id=3130

#include <stdio.h>
#include <math.h>
#include <memory.h>
#include <algorithm>
using namespace std;

typedef double Type;

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);}
inline Type cheng(point b,point c)
{return b.x*c.y-c.x*b.y;}

//���
inline Type dcheng(point a,point b,point c)
{return (b.x-a.x)*(c.x-a.x)+(c.y-a.y)*(b.y-a.y);}
inline Type dcheng(point b,point c)
{return b.x*c.x+c.y*b.y;}

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

point crosspoint(line l1,line l2)
{
    Type p1=cheng(l2.a,l1.a,l2.b),
         p2=cheng(l2.a,l2.b,l1.b);
    if(p1+p2==0)return l1.a;

    point c;
    c.x=(p1*l1.b.x+p2*l1.a.x)/(p1+p2);
    c.y=(p1*l1.b.y+p2*l1.a.y)/(p1+p2);
    return c;
}

bool check( point p[], int n ) {
    int i, j, ii, jj, k;
    point o;
    line l;
    for( i=0; i<n; i++ ) {
        ii = (i+1)%n;
        l.a = p[i]; l.b = p[ii];
        for( j=i+1; j<n; j++ ) {
            jj = (j+1)%n;
            if( (p[i].x-p[ii].x)*(p[j].y-p[jj].y) != (p[i].y-p[ii].y)*(p[j].x-p[jj].x) ) {
                o = crosspoint( l, line( p[j], p[jj] ) );
                for( k=0; k<n; k++ )
                    if( cheng( p[k], o, p[(k+1)%n] ) > 1e-7 )
                        break;
                if( k >= n )
                    return true;
            }
        }
    }
    return false;
}



point p[100];

int main( ) {
    int i, n;
    while( true ) {
        scanf( "%d", &n );
        if( n == 0 ) break;

        for( i=0; i<n; i++ )
            scanf( "%lf%lf", &p[i].x, &p[i].y );
        
        printf( "%dn", check( p, n ) );
    }
    return 0;
}