3130.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Source

Problem Id:3130  User Id:fzk 
Memory:44K  Time:15MS
Language:G++  Result:Accepted

Source 

#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( "%d\n", check( p, n ) );
	}
	return 0;
}