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

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

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