points to the distance segment.txt

1.表达式求值；2.二分匹配模板；3.最大流；4.点到线段的距离；5.字符串字典顺序

// distance to a segment
// construct a line perpendicular to the segment
// if the two end points of the line is on the same side of this line
// return min distance to the end points
// return distance to line otherwise
// 求点到线段的距离
// 输入点的坐标和线段两端点的坐标
#include <math.h>

const double EPS = 1e-8;

struct point
{
	double x, y;
};

double min ( double x1, double x2 )
{
	if ( x1 - x2 >= EPS )
		return ( x2 );
	else if ( x1 - x2 < -EPS )
		return ( x1 );
}

double distanceToSegment ( point v, point p1, point p2 ) //点到线段的距离
{
	point u;
	u.x = v.x + p2.y - p1.y;
	u.y = v.y - ( p2.x - p1.x );

	double len = sqrt ( ( p1.x - p2.x ) * ( p1.x - p2.x ) + ( p1.y - p2.y ) * ( p1.y - p2.y ) );
	double a = ( p1.x - v.x ) * ( p2.y - v.y ) - ( p1.y - v.y ) * ( p2.x - v.x );
	double dToL = fabs ( a ) / len;

	double dToP1 = sqrt ( ( p1.x - v.x ) * ( p1.x - v.x ) + ( p1.y - v.y ) * ( p1.y - v.y ) );
	double dToP2 = sqrt ( ( p2.x - v.x ) * ( p2.x - v.x ) + ( p2.y - v.y ) * ( p2.y - v.y ) );

	double a1 = ( u.x - p1.x ) * ( v.y - p1.y ) - ( u.y - p1.y ) * ( v.x - p1.x );
	double a2 = ( u.x - p2.x ) * ( v.y - p2.y ) - ( u.y - p2.y ) * ( v.x - p2.x );
	bool ifSameSide = false;
	if ( ( a1 >= EPS && a2 >= EPS ) || ( a1 <= -EPS && a2 <= -EPS ) )
		ifSameSide = true;

	return ifSameSide ? min ( dToP1, dToP2 ) : dToL;
}