poj3433RoadAccident

题目&＃xff1a;给你两辆车的左后方和左前方的坐标&＃xff0c;车宽和速度&＃xff0c;将车看成矩形并分成四部分&＃xff0c;问两辆车相撞的位置编号。

分析&＃xff1a;计算几何、线与线的关系判断。

            首先&＃xff0c;先将分别运动的两车转移到相对参考系&＃xff0c;利用速度向量做差即可。

            然后&＃xff0c;判断两车相撞&＃xff0c;可以分成三种情况&＃xff1a;点对点&＃xff0c;点对线&＃xff0c;线对线。由于点撞到点&＃xff0c;一定撞到线上。

                        线对线可以转化成点对线&＃xff0c;所以将所有情况转换成点对线即可。将四个顶点和各边的中点构成集合A。

                        将四个顶点和相邻中点的连线构成的8条线段构成集合B。利用A集合的点做速度v方向的射线。

                        如果相撞&＃xff0c;则射线一定与线段相交。计算A中的点与交点的距离&＃xff0c;取最小的即为最先相撞的部分。

            最后&＃xff0c;让两辆车分别向对方相撞&＃xff08;速度相反&＃xff09;&＃xff0c;整理结果即可。

注意&＃xff1a;1.精度问题&＃xff1b;2.相撞的区域不一定是最优解&＃xff0c;如下图&＃xff0c;结果应该是1 1。

#include
#include
#include
#include #define esp 1e-6using namespace std;//点结构
typedef struct pnode
{double x,y;int id;pnode( double a, double b ){x &＃61; a;y &＃61; b;}pnode( double a, double b, int i ){x &＃61; a;y &＃61; b;id &＃61; i;}pnode(){}
}point;//直线线结构
typedef struct lnode
{double x,y,dx,dy;lnode( point a, point b ){x &＃61; a.x;y &＃61; a.y;dx &＃61; b.x-a.x;dy &＃61; b.y-a.y;}lnode(){}
}line;//线段结构
typedef struct snode
{point p1,p2;int id;snode( point a, point b, int i ){p1 &＃61; a;p2 &＃61; b;id &＃61; i;}snode(){}
}segment;//车结构
typedef struct cnode
{point p[8];segment s[8];
}car;//构造结点和线段
car madecar( double x, double y, double u, double v, double w )
{car Car;Car.p[0] &＃61; point( x, y, 1 );Car.p[2] &＃61; point( u, v, 2 );double d &＃61; sqrt((x-u)*(x-u)&＃43;(y-v)*(y-v));point r &＃61; point( (v-y)*w/d, (x-u)*w/d );Car.p[4] &＃61; point( u&＃43;r.x, v&＃43;r.y, 3 );Car.p[6] &＃61; point( x&＃43;r.x, y&＃43;r.y, 4 );for ( int i &＃61; 0 ; i <8 ; i &＃43;&＃61; 2 ) {point m;m.x &＃61; (Car.p[i].x&＃43;Car.p[(i&＃43;2)%8].x)/2;m.y &＃61; (Car.p[i].y&＃43;Car.p[(i&＃43;2)%8].y)/2;m.id &＃61; min(Car.p[i].id,Car.p[(i&＃43;2)%8].id);Car.p[i&＃43;1] &＃61; m;}for ( int i &＃61; 0 ; i <8 ; &＃43;&＃43; i ) {Car.s[i] &＃61; segment( Car.p[i], Car.p[(i&＃43;1)%8], 0 );Car.s[i].id &＃61; (i&＃43;1)%8/2&＃43;1;}return Car;
}//两点间距离
double dist( point a, point b )
{return sqrt((a.x-b.x)*(a.x-b.x)&＃43;(a.y-b.y)*(a.y-b.y));
}//直线相交判断
bool lcrossl( line a, line b )
{ double t1 &＃61; b.dx*(a.y-b.y)-b.dy*(a.x-b.x); double t2 &＃61; b.dx*(a.y&＃43;a.dy-b.y)-b.dy*(a.x&＃43;a.dx-b.x); return (t1-esp)*(t2-esp) <&＃61; 0;
}//求直线交点
point crosspoint( line l, line m )
{ point a &＃61; point( m.x, m.y );point b &＃61; point( m.x&＃43;m.dx, m.y&＃43;m.dy );if ( m.dx*l.dy &＃61;&＃61; m.dy*l.dx ) { if ( dist( point( l.x, l.y ), a ) } //结果结构
typedef struct anode
{int id1,id2;double dis;anode( int a, int b, double d ){id1 &＃61; a;id2 &＃61; b;dis &＃61; d;}
}answer;//判断a撞向b
answer crash( car a, car b, point v )
{double dis &＃61; 1e20;int id1 &＃61; 1,id2 &＃61; 1;for ( int i &＃61; 0 ; i <8 ; &＃43;&＃43; i )for ( int j &＃61; 0 ; j <8 ; &＃43;&＃43; j ) {point c &＃61; point( a.p[i].x&＃43;v.x, a.p[i].y&＃43;v.y );line l &＃61; line( b.s[j].p1, b.s[j].p2 );if ( lcrossl( l, line( a.p[i], c ) ) ) {point e &＃61; crosspoint( line( a.p[i], c ), l );double d &＃61; dist( a.p[i], e );if ( fabs(dis-d) a.p[i].id ) id1 &＃61; a.p[i].id;if ( id2 > b.s[j].id ) id2 &＃61; b.s[j].id;}if ( dis-esp > d ) {dis &＃61; d;id1 &＃61; a.p[i].id;id2 &＃61; b.s[j].id;}}}return answer( id1, id2, dis );
}int main()
{double x1,y1,u1,v1,w1,s1,x2,y2,u2,v2,w2,s2;while ( ~scanf("%lf%lf%lf%lf%lf%lf",&x1,&y1,&u1,&v1,&w1,&s1) ) {scanf("%lf%lf%lf%lf%lf%lf",&x2,&y2,&u2,&v2,&w2,&s2);//将输入转化成几何模型&＃xff08;8个点&＃43;8条线段&＃xff09; car A &＃61; madecar( x1, y1, u1, v1, w1 );car B &＃61; madecar( x2, y2, u2, v2, w2 );//计算速度向量 double d1 &＃61; sqrt((x1-u1)*(x1-u1)&＃43;(y1-v1)*(y1-v1));point V1 &＃61; point( (u1-x1)*s1/d1, (v1-y1)*s1/d1 );double d2 &＃61; sqrt((x2-u2)*(x2-u2)&＃43;(y2-v2)*(y2-v2));point V2 &＃61; point( (u2-x2)*s2/d2, (v2-y2)*s2/d2 );answer an1 &＃61; crash( A, B, point( V1.x-V2.x, V1.y-V2.y ) );answer an2 &＃61; crash( B, A, point( V2.x-V1.x, V2.y-V1.y ) );if ( fabs(an1.dis-an2.dis) }