3178.txt

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

Source

Problem Id:3178  User Id:fzk 
Memory:192K  Time:218MS
Language:C++  Result:Accepted

Source 

#include <stdio.h>
#include <math.h>

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

double dis(point a,point b)
{
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

bool can[151][151] = { false };
point p[151];
point o[151];
int r, n, g;

void clac_can( ) {
	int i, j, k;
	bool sign[151] = { false };

	for( i=0; i<n; i++ ) {
		for( j=0; j<g; j++ ) {
			if( dis( p[i], o[j] ) <= r ) {
				sign[i] = true;
				break;
			}
		}
	}

	for( i=0; i<n; i++ ) {
		if( !sign[i] ) {
			for( j=i+2; j<n; j++ ) {
				if( !sign[j] ) {
					double len = dis( p[i], p[j] );
					can[i][j] = true;
					for( k=0; k<g; k++ ) {
						if( dcheng( p[i], p[j], o[k] ) > 0 && dcheng( p[j], p[i], o[k] ) > 0
							&& fabs( cheng( p[i], p[j], o[k] ) ) / len <= r ) {
							can[i][j] = false;
							break;
						}
					}
				}
			}//for
		}
	}//for
	can[0][n-1] = false;
}

int ans[151][151] = { 0 };

void doit( ) {
	int i, j, l;
	for( l=2; l<=n; l++ ) {
		for( i=0; i<=n-l; i++ ) {
			int t = 0, max = 0;
			for( j=i+1; j<i+l; j++ )
				if( ( t = ans[i][j] + ans[j][i+l] + can[i][j] ) > max )
					max = t;
			ans[i][i+l] = max;
		}
	}

	printf( "%d\n", ans[0][n] );
}

int main( ) {
	int i;
	
	scanf( "%d%d%d", &n, &g, &r );
	
	for( i=0; i<n; i++ )
		scanf( "%lf%lf", &p[i].x, &p[i].y );

	for( i=0; i<g; i++ )
		scanf( "%lf%lf", &o[i].x, &o[i].y );
	
	clac_can( );
	doit( );

	return 0;
}