zoj1744.cpp

最近在acm.zju.edu.cn上通过的题目的代码

#include<iostream>
#include<cstdio>
#include<cmath>

using namespace std;

const int maxn = 200;
const double eps = 1e-8;

int dcmp( double x ) {
	if( x < -eps ) return -1; return x > eps;
}

struct Point{
	double x, y;
	Point ( double xx = 0, double yy = 0 ) : x(xx),y(yy) {};
	double cross( const Point& a, const Point& b ) const
	{ return ( a.x-x ) * ( b.y-y ) - ( a.y-y ) * ( b.x-x ); }
};

bool SegCross ( const Point& p1, const Point& p2, const Point& p3, const Point & p4 ){
	if( max( p1.x, p2.x ) + eps < min( p3.x, p4.x ) ||
		max( p3.x, p4.x ) + eps < min( p1.x, p2.x ) ||
		max( p1.y, p2.y ) + eps < min( p3.y, p4.y ) ||
		max( p3.y, p4.y ) + eps < min( p1.y, p2.y ) ) return 0;
	int d1 = dcmp( p3.cross( p4, p2 ) );
	int d2 = dcmp( p3.cross( p4, p1 ) );
	int d3 = dcmp( p1.cross( p2, p4 ) );
	int d4 = dcmp( p1.cross( p2, p3 ) );
	if( d1 * d2 == 1 || d3 * d4 == 1 ) return 0;
	//if( d1 == 0 && d2 == 0 && d3 == 0 && d4 == 0 ) return 1;
	return 1;
}

int n, N;
Point s, t;
Point ls[maxn*2];

bool readr(){
	scanf("%d", &n); 
	if (n == 0) return false;
    N = 2 * n;
	for( int i = 0; i < N; ++ i )
		scanf("%lf%lf", &ls[i].x, &ls[i].y );
    for (int i = 0; i < n; i++){
        double dx = ls[i*2+1].x - ls[i*2].x;
        double dy = ls[i*2+1].y - ls[i*2].y;
        ls[i*2+1].x += dx * 1e-6; ls[i*2+1].y += dy * 1e-6;
        ls[i*2].x -= dx * 1e-6; ls[i*2].y -= dy * 1e-6;
    }
	ls[N++] = Point(0, 0); ls[N++] = Point(51, 51);
	return true;
}

bool mk[maxn*2];
bool g[maxn*2][maxn*2];

void dfs( int u ){
	if (mk[N - 1]) return; mk[u] = 1;
	for( int v = 0; v < N; ++ v ) if( !mk[v] && g[u][v] ) dfs( v );
}

void solvr (){
	int i, j, k;
	for( i = 0; i < N; ++ i )
		for( j = i+1; j < N; ++ j ){
			g[i][j] = 1;
			for( k = 0; g[i][j] && k < n; ++ k ) if( i/2 != k && j/2 != k )
				g[i][j] &= !SegCross( ls[i], ls[j], ls[k*2], ls[k*2+1] );
			g[j][i] = g[i][j];
		}
		
	memset( mk, 0, sizeof( mk ) );
	dfs( N-2 );
	printf("%s\n", mk[N-1] ? "no" : "yes" );
}

int main (){
	while (readr()) solvr();
	return 0;
}