absi2011's Blog & Daily Life.

全新的开始       我要省选翻盘       I wanna AK in 高考\化学       自此,生无可恋
记录高考路程中的各种考试
[这个blog需要恢复] 沈阳赛区比赛订正情况

[这个Blog需要恢复]区域赛-乌鲁木齐赛区订正

absi2011 posted @ Sep 11, 2017 01:42:36 PM in 网上比赛 with tags 计算几何 acm 小高考 区域赛 , 556 阅读

因为我们离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;
}
IndusInd bank corpor 说:
Aug 07, 2022 03:58:15 PM

Indusind Bank is quite well known as it provides all essential banking services without much fees that has garnered them a lot of customers across the years. If you are someone who has an IndusInd bank account then you might know how great their service is. IndusInd bank corporate login They provide different banking services from setting up of savings, personal account, providing of loans, credit and debit cards as well. Now with internet banking on the rise, they have made their IndusInd bank login process quite easy. In this article we will help you learn more about it.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter