题意 两条狗啊，同时跑，，同时结束，各自跑各自的道路，问跑的过程中，他们最大距离和最小距离的差；
方法 恶心一点就是，最大最小距离的求解方法，假设两只狗都只有一条线段要跑，则可以判定在端点处有最大值，最小值的求解方法就是，把一条狗的奔跑方向分解成另一个狗的奔跑方向 + 另外一个向量，这样这条狗相对于另外一条狗处于相对静止；只要求点到线段的最小距离便是； 如果有两段以上的线段；考虑第一条线段；肯定会有一条狗先跑完第一段，另外一条狗没有跑完第一段，根据比例关系我们可以知道那条没有跑完的狗跑到那里了，因此可以得到那条没有跑完的狗的终点坐标；然后这条没有跑完的狗的下一条线段，就是这个终点到，，，，当前自己的终点；就这样一直跑下去
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<functional>
#define eps 1e-9
#include<vector>
using namespace std;
const double PI = acos(-1.0);
int dcmp( double x ){ if( abs(x) < eps ) return ;else return x < ?-:; }
struct point{
double x,y;
point( double x = ,double y = ):x(x),y(y){}
}node[]; typedef point Vector;
struct segment{
point a,b; segment(){}
segment(point _a,point _b){a=_a,b=_b;}
};
struct circle{
point c; double r; circle(){}
circle(point _c, double _r):c(_c),r(_r) {}
point PPP(double a)const{return point(c.x+cos(a)*r,c.y+sin(a)*r);}
};
struct line{
point p,v; double ang;
line() {}
line( const point &_p, const point &_v):p(_p),v(_v){ang = atan2(v.y, v.x);}
inline bool operator < (const line &L)const{return ang < L.ang;}
};
point operator + (point a,point b){return point( a.x + b.x,a.y + b.y );}
point operator - (point a,point b){return point( a.x - b.x,a.y - b.y );}
point operator * (point a,double b){return point( a.x*b,a.y*b );}
point operator / (point a,double b){ return point( a.x/b,a.y/b );}
bool operator < (const point &a, const point &b ){return a.x < b.x || (a.x == b.x && a.y < b.y );}
bool operator == (const point &a, const point &b ){return (dcmp(a.x - b.x) == && dcmp(a.y - b.y) == );}
bool operator != (const point &a,const point &b ){return a == b?false:true;} double Dot( point a,point b ){return a.x*b.x + a.y*b.y;} // 点到点的距离；
double Length( point a ){return sqrt( Dot( a,a ) );} // 向量长度
double Angle( point a,point b ){ return acos( Dot(a,b)/Length(a)/Length(b) );} // 两个向量的角度
double D_T_D(const double ° ){ return deg/*PI; }
// 向量旋转 rad 度数
point Rotate( point a, double rad ){
return point( a.x*cos(rad)-a.y*sin(rad),a.x*sin(rad)+a.y*cos(rad) );
}
// 向量的 法线向量 的单位向量
point Normal( point a ){
double L = Length(a); return point(-a.y/L,a.x/L);
}
// 叉积计算
double Cross( point a,point b ){
return a.x*b.y - a.y*b.x;
}
// 获取 两个向量叉积
double get_Mix( point a,point b,point pot ){
a.x = a.x - pot.x; a.y = a.y - pot.y;
b.x = b.x - pot.x; b.y = b.y - pot.y;
return Cross( a,b );
}
// 直线相交求交点；
point get_line_inter( point p,point v, point q,point w ){
point u = p - q;
double t = Cross(w,u)/Cross(v,w);
return p+v*t;
}
// p点到直线 的距离
double dis_p_line( point p,point a,point b ) {
point v1 = b-a, v2 = p-a;
return abs( Cross(v1,v2)/Length(v1) );
}
//点在直线上的投影
inline point GetLineProjection(const point &p,const point &a,const point &b){
point v=b-a;
return a+v*(Dot(v,p-a)/Dot(v,v));
}
// 点到线段的距离
double dis_p_segm( point p,point a,point b ){
if( a == b )return Length( p-a );
point v1 = b-a,v2 = p-a,v3 = p-b;
if( dcmp(Dot(v1,v2)) < )return Length(v2);
else if( dcmp(Dot( v1,v3)) > )return Length(v3);
else return abs(Cross( v1,v2 ))/Length(v1);
}
//海伦公式 三条边
double Heron(double a,double b,double c){
double p=(a+b+c)/;
return sqrt(p*(p-a)*(p-b)*(p-c));
}
// 多边形面积 从p[0] 开始，p[n] 结束
double ploy_area( point *p,int n ){
double area = ;
for( int i = ; i < n-; i++ )
area += Cross( p[i]-p[],p[i+]-p[] );
return area/2.0;
}
// 线段相交判断 先必须去掉不相交的状态；再判断方向
bool get_set( point a,point b,point c,point d ){
if( min( a.x,b.x ) <= max( c.x,d.x ) && min( a.y,b.y ) <= max( c.y,d.y ) &&
min( c.x,d.x ) <= max( a.x,b.x ) && min( c.y,d.y ) <= max( a.y,b.y ) &&
Cross( c-b,a-b )*Cross( d-b,a-b ) <= &&
Cross( a-d,c-d )*Cross( b-d,c-d ) <=
) return true;
return false;
}
// 线段 直线 平行判断只需要对应向量平行；
bool get_pall( point a,point b,point c,point d ){
if( Cross( a-b,c-d ) == )return true;
return false;
}
// 直线 重合判断 只需要 一条直线的两点都在直线方向
bool get_doub( point a,point b,point c,point d ){
if( Cross( d-b,a-b ) == && Cross( c-b,a-b ) == )return ;
return ;
}
// 获取 线段 交点；依据 叉积判断
point get_pot( point a,point b,point c,point d ){
point temp;
temp.x = ( c.x*Cross(b-a,d-a) - d.x*Cross(b-a,c-a) )/( Cross(b-a,d-a) - Cross(b-a,c-a) );
temp.y = ( c.y*Cross(b-a,d-a) - d.y*Cross(b-a,c-a) )/( Cross(b-a,d-a) - Cross(b-a,c-a) );
return temp;
}
//获取直线的交点 同时也可以是线段的交点；
point get_ppp( point a,point b,point c,point d ){
double a0 = a.y - b.y; double b0 = b.x - a.x; double c0 = a.x*b.y - b.x*a.y;
double a1 = c.y - d.y; double b1 = d.x - c.x; double c1 = c.x*d.y - d.x*c.y;
double D = a0*b1 - a1*b0; point temp;
temp.x = ( b0*c1 - b1*c0 )/D;
temp.y = ( a1*c0 - a0*c1 )/D;
return temp;
}
//点pot 是否 在线段 ab 上 只需 叉积等于0 点积等于0
bool online( point a,point b,point pot ){
if( Cross( a - pot,b - pot ) == && Dot( a - pot,b - pot ) <= )return ;
return ;
}
int top,res[]; // 凸包 ( 起点 0 ) ( n 个点 ) 自己写的，，需要改进 改进；
void GRA( int n )
{
sort( node,node+n ); // 先排序
top = ; res[] = ; res[] = ;// 从第0位开始放；前两位不管
for( int i = ; i <= n; i++ ){
while( top && get_Mix( node[i],node[res[top]],node[res[top-]] ) > )top--;
res[++top] = i;
}
int k = top;
for( int i = n-; i >= ; i-- ){
while( top > k && get_Mix( node[i],node[res[top]],node[res[top-]] ) > )top--;
res[++top] = i;
}
top--; // 会添加进去最后一个点
}
//求两圆相交
int C_T_C( circle c1,circle c2,point &p1,point &p2 ){
double d = Length( c1.c- c2.c );
if( dcmp( d ) == ) {
if( dcmp( c1.r-c2.r ) == ) return -;//两圆重合
return ;
}
if( dcmp( c1.r + c2.r - d ) < ) return ;
if( dcmp( fabs( c1.r - c2.r ) - d ) > ) return ;
double a = Angle( c2.c - c1.c,point( , ) );
double da = acos(( c1.r * c1.r + d * d - c2.r * c2.r )/( * c1.r * d ) );
p1 = c1.PPP( a - da ); p2 = c1.PPP( a + da );
if( p1 == p2 ) return ;
return ;
}
//圆与直线交点 返回交点个数
int C_T_L( line L,circle C,point &p1,point &p2){
double a = L.v.x, b = L.p.x - C.c.x, c = L.v.y, d = L.p.y-C.c.y;
double e = a*a + c*c, f = *(a*b+c*d), g = b*b + d*d -C.r*C.r;
double delta = f*f - *e*g;
if( dcmp(delta) < ) return ;//相离
if( dcmp(delta) == ) {//相切
p1 = p1 = L.p + L.v*( -f/(*e) );
return ;
}//相交
p1 = ( L.p + L.v * ( -f-sqrt(delta) )/( *e ) );
p2 = ( L.p + L.v * ( -f+sqrt(delta) )/( *e ) );
return ;
}
//点与圆的切线；
int get_P_C_inter( point p,circle c, point *v )
{
point u = c.c - p; double dist = Length(u);
if( dist < c.r )return ;
else if( dcmp( dist - c.r) == ){
v[] = Rotate( u,PI/ );
return ;
}else {
double ang = asin( c.r/dist );
v[] = Rotate(u,-ang);
v[] = Rotate(u,+ang);
return ;
}
return -;
}
point A[],B[];
int main( )
{
int T,N,M,cas = ;scanf("%d",&T);
while( T-- )
{
double sum1 = ; double sum2 = ;
scanf("%d%d",&N,&M);
for( int i = ; i <= N; i++ ){
scanf("%lf%lf",&A[i].x,&A[i].y);
if( i != )sum1 += Length( A[i]-A[i-] );
}
for( int i = ; i <= M; i++ ){
scanf("%lf%lf",&B[i].x,&B[i].y);
if( i != )sum2 += Length( B[i]-B[i-] );
}
double Bi = sum1/sum2;
double Max = ;double Min = (<<); int ans1 = ; int ans2 = ;
point sta = A[]; point end = A[]; point u = B[]; point v = B[];
while( ans1 <= N && ans2 <= M )
{
if( Length(end-sta)/Length(v-u) > Bi )
{
point tp; tp = sta + (end-sta)*Length(v-u)*Bi/Length(end-sta);
Max = max( Max,max( Length(tp-v),Length(sta-u) ) );
point temp; temp = sta + ( (tp - sta) - ( v - u ) );
Min = min( Min, dis_p_segm( u,sta,temp ) );
sta = tp; u = v; v = B[++ans2];
}else
{
point tp; tp = u + (v-u)*Length(end-sta)/Bi/Length(v-u);
Max = max( Max,max( Length(end-tp),Length(sta-u) ) );
point temp; temp = sta + ( (end - sta) - ( tp - u ) );
Min = min( Min, dis_p_segm( u,sta,temp ) );
u = tp; sta = end; end = A[++ans1];
}
}
printf("Case %d: %.lf\n",cas++,Max-Min);
}
return ;
}