题目链接：
https://nanti.jisuanke.com/t/A1248
Description
Two out-of-control cars crashed within about a half-hour Wednesday afternoon on Deer
Park Avenue. This accident alarmed the district government.
It jumpstarted a vibrant new technology to predict potential car accidents.
Engineers depicted a moving vehicle as a triangle with directional movement.
Three two dimeniaonal points (x1?,y1?),(x2?,y2?) and(x3?,y3?) restrict the span of a vehicle.
Its moverment is a uniform linear motion described by a vector (dx?,dy?).
That is say that after one second, the i-th endpoint of the emulational vehicle, the triangle, should be at(xi?+dx?,yi?+dy?).
The core function of this technology is simple.
For two given triangles, corresponding to two vehicles, predict that if they would collide in the near future.
Two triangles are considered collided, if they touched in some points or their intersection is not empty.
The first line of the input contains an integer tt specifying the number of test cases.
Each test case is consist of two lines and each line contains eight integers x1?, y1?, x2?, y2?, x3?, y3? and dx?, dy?, to describe a vehicle and its movement.
The absolute value of each input number should be less than or equal to 10^9.
For each test case output the case number first. Then output YES if they would collide in the near future, or NO if they would never touch each other.
Input
30 1 2 1 1 3 1 0 9 2 10 4 8 4 -1 00 1 2 1 1 3 2 0 9 2 10 4 8 4 3 00 1 2 1 1 3 0 0 0 4 1 6 -1 6 1 -2Output
Case #1: YES Case #2: NO Case #3: YES
Description
给出两个三角形的三个顶点坐标和其速度向量，问两个三角形是否可能相交
Input
第一行一整数TT表示用例组数，每组用例输入两行，一行八个整数分别表示三角形三点坐标和速度向量，绝对值均不超过
Output
如果两个三角形可以相交则输出YESYES，否则输出NO
//注意输出格式
思路：
固定一个三角形，另一个三角形用相对速度运动
判断线段ab是否和从c点出发， 以vv为速度向量的射线相交，
如果ab与v平行，c点只有在直线ab上才可能与线段ab相交，此时根据
解出t如果非负说明c可以运动到a，同理
解出t如果非负说明c可以运动到b，如果这两种情况都不行说明不相交；
如果ab与v不平行，那么直线ab与过c点以v为方向的直线必然相交，如果以c为起点方向为v的射线经过直线ab，则需要
在t>=0时在直线
化简后为
， 同时为了射线经过线段ab则需要向量v在向量(a-c) 和向量（b-c) 之间 即
保证两个式子成立即射线经过线段，反之则不经过线段
This is the code
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<iomanip>
#include<list>
#include<map>
#include<queue>
#include<sstream>
#include<stack>
#include<string>
#include<set>
#include<vector>
using namespace std;
#define PI acos(-1.0)
#define EXP exp(1)
#define pppp cout<<endl;
#define EPS 1e-8
#define LL long long
#define ULL unsigned long long //1844674407370955161
#define INT_INF 0x3f3f3f3f //1061109567
#define LL_INF 0x3f3f3f3f3f3f3f3f //4557430888798830399
// ios::sync_with_stdio(false);
// 那么cin, 就不能跟C的 scanf，sscanf, getchar, fgets之类的一起使用了。
const int dr[]= {0, 0, -1, 1, -1, -1, 1, 1};
const int dc[]= {-1, 1, 0, 0, -1, 1, -1, 1};
inline int read()//输入外挂
{int ret=0, flag=0;char ch;if((ch=getchar())=='-')flag=1;else if(ch>='0'&&ch<='9')ret = ch - '0';while((ch=getchar())>='0'&&ch<='9')ret=ret*10+(ch-'0');return flag ? -ret : ret;
}
struct Point
{LL x,y;Point(LL x=0LL, LL y=0LL):x(x),y(y){}Point operator -(const Point &rh )const{return Point(x-rh.x, y-rh.y);}
} ;
bool flag;
int Mul(Point a, Point b)//叉积
{LL t=a.x*b.y-b.x*a.y;if(t>0)return 1;//锐角else if(t<0)return -1;//钝角elsereturn 0;//平行
}
bool check(Point a, Point b, Point c, Point v)//以c为起点方向为v的射线 是否经过线段abif(Mul(b-a, v)==0)//线段与向量v平行{if(Mul(a-c, b-c)!=0)//s点c不在直线ab上return false;else if(v.x*(a.x-c.x)>=0 || v.x*(b.x-c.x)>=0) // 点c在线段ab上return true;elsereturn false;}else{if(Mul(c-a, b-a)*Mul(b-a,v)>=0)//c为起点，v为方向的射线经过线段ab{if(Mul(a-c, v)*Mul(b-c, v)<=0)//c为起点，v为方向的射线经过线段ab，即向量v在向量a-c与b-c之间return true;elsereturn false;}elsereturn false;}return false;
}
void Slove(Point p1[],Point p2[], Point v)
{for(int i=0;i<3;++i)for(int j=0;j<3;++j)for(int k=j+1;k<3;++k)if(check(p2[j],p2[k],p1[i],v))flag=true;
}
int main()
{int T;int Case=1;Point p1[4],p2[4],v1,v2;scanf("%d",&T);while(T--){for(int i=0;i<3;++i)scanf("%lld%lld",&p1[i].x,&p1[i].y);scanf("%lld%lld",&v1.x,&v1.y);for(int i=0;i<3;++i)scanf("%lld%lld",&p2[i].x,&p2[i].y);scanf("%lld%lld",&v2.x,&v2.y);flag=false;Slove(p1,p2,v1-v2);Slove(p2,p1,v2-v1);printf("Case #%d: ",Case++);if(flag)printf("YES\n");elseprintf("NO\n");}return 0;
}