因为我们离AK就差一个B所以只写了B

B是一个计算几何,我们队现场直播想偏思路然后滚粗..

现场9题的全是卡D卡I的,就我们一个队卡了B...........

B题有毒!

B题题意:

给两个三角形,给出它们的运动速度(向量形式)

问在有生之年是否会有一个时刻相撞(多测,每个输出YES/NO)

(相撞:有共同的点或者面积)

三角形的坐标-1e9~1e9

速度向量-1e9~1e9

做法:

重新建个参考系,把一个车固定下来,速度加到另一个车上

然后判断这个车的三个点的射线是否会撞到另一个三角形上

然后再对另一个车做同样操作

如果两次都撞不上就是NO

特判:相对静止的时候,如果点在三角形内则YES否则NO

反正过了sample,system test等过一段时间交了再看看吧

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct point
{
    int x;
    int y;
    point (int xx=0,int yy=0)
    {
        x=xx;
        y=yy;
    }
    friend point operator + (const point &a,const point &b)
    {
        return point(a.x+b.x,a.y+b.y);
    }
    friend long long operator * (const point &a,const point &b)
    {
        return (long long)a.x*b.y-(long long)b.x*a.y;
    }
    friend point operator - (const point &a,const point &b)
    {
        return point(a.x-b.x,a.y-b.y);
    }
    friend bool operator == (const point &a,const point &b)
    {
        return (a.x==b.x)&&(a.y==b.y);
    }
    void read()
    {
        scanf("%d%d",&x,&y);
    }
};
bool in_triangle(point a1,point a2,point a3,point b)
{
    int t1=(a1-b)*(a2-b);
    int t2=(a2-b)*(a3-b);
    int t3=(a3-b)*(a1-b);
    if ((t1<=0)&&(t2<=0)&&(t3<=0))
    {
        return true;
    }
    if ((t1>=0)&&(t2>=0)&&(t3>=0))
    {
        return true;
    }
    return false;
}
bool cross(point x1,point y1,point x2,point y2)
{
    long long t1=(x2-x1)*(x2-y1);
    long long t2=(y2-x1)*(y2-y1);
    if (((t1<0)&&(t2<0))||((t1>0)&&(t2>0)))
    {
        return false;
    }
    t1=(x1-x2)*(x1-y2);
    t2=(y1-x2)*(y1-y2);
    if (((t1<0)&&(t2<0))||((t1>0)&&(t2>0)))
    {
        return false;
    }
    return true;
}
bool check(point a1,point a2,point a3,point b,point v)
{
    int num1;
    if (v.x!=0) num1=max((1000000001-b.x)/v.x+1,(-1000000001-b.x)/v.x+1); else num1=1000000001;
    int num2;
    if (v.y!=0) num2=max((1000000001-b.y)/v.y+1,(-1000000001-b.y)/v.y+1); else num2=1000000001;
    point c=point(min(num1,num2)*v.x,min(num1,num2)*v.y)+b;
    if (cross(a1,a2,b,c)||cross(a1,a3,b,c)||cross(a2,a3,b,c))
    {
        return true;
    }
    return false;
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int t;
    scanf("%d",&t);
    int zu;
    for (zu=0;zu<t;zu++)
    {
        printf("Case #%d: ",zu+1);
        point a1,a2,a3;
        a1.read();
        a2.read();
        a3.read();
        point va;
        va.read();
        point b1,b2,b3;
        b1.read();
        b2.read();
        b3.read();
        point vb;
        vb.read();
        va=va-vb;
        vb=point()-va;
        if (va==point(0,0))
        {
            if (in_triangle(a1,a2,a3,b1)||in_triangle(a1,a2,a3,b2)||in_triangle(a1,a2,a3,b3)||in_triangle(b1,b2,b3,a1)||in_triangle(b1,b2,b3,a2)||in_triangle(b1,b2,b3,a3))
            {
                puts("YES");
            }
            else
            {
                puts("NO");
            }
        }
        else
        {
            if (check(a1,a2,a3,b1,vb)||check(a1,a2,a3,b2,vb)||check(a1,a2,a3,b3,vb)||check(b1,b2,b3,a1,va)||check(b1,b2,b3,a2,va)||check(b1,b2,b3,a3,va))
            {
                puts("YES");
            }
            else
            {
                puts("NO");
            }
        }
    }
    return 0;
}