HDU-5572-An Easy Physics Problem

ACM模版

描述

题解

计算几何问题,给定一质点的位置和速度,给定一个圆柱的圆心和半径,质点移动如果撞上圆柱则发生弹性碰撞。问这个点是否可以经过另一个质点。

这个题比较直观的想法是求角度,但是这样容易存在精度上的误差,所以可以采用求一个点关于直线的对称点来求出弹性碰撞后的轨迹,判断另一个质点是否在这个质点的运动轨迹上即可。

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const double EPS = 1e-8;

int cmp(double x)
{
    if (fabs(x) < EPS)
    {
        return 0;
    }
    else
    {
        return x > 0 ? 1 : -1;
    }
}

typedef struct node
{
    double x, y;

    void read()
    {
        scanf("%lf%lf", &x, &y);
    }
} point, speed;

point PA, PB;
speed SA;

struct circle
{
    point o;
    int r;

    void read()
    {
        scanf("%lf%lf%d", &o.x, &o.y, &r);
    }
} C;

node operator + (node a, node b)
{
    return {a.x + b.x, a.y + b.y};
}

node operator - (node a, node b)
{
    return {a.x - b.x, a.y - b.y};
}

node operator * (double p, node a)
{
    return {a.x * p, a.y * p};
}

double dot(node a, node b)
{
    return a.x * b.x + a.y * b.y;
}

double dis(node a)
{
    return sqrt(dot(a, a));
}

double cross(node a, node b)
{
    return a.x * b.y - b.x * a.y;
}

node GetLine(node P, node A, node B)
{
    node V = B - A;
    node ans = A + (dot(V, P - A) / dot(V, V)) * V;
    return ans;
}

double d;
node AngleA, AngleB, head;

void GetAnglePoint(point PA, speed SA, circle C)
{
    node A = PA, B = PA + SA;
    if (dis(C.o - B) > dis(C.o - A))
    {
        A = PA + SA;
        B = PA;
    }
    head = GetLine(C.o, A, B);

    d = dis(head - C.o);
    if (cmp(d - C.r) < 0)
    {
        double l = sqrt((double)C.r * C.r - d * d);
        AngleA = head + l / dis(B - A) * (B - A);
        AngleB = head - l / dis(B - A) * (B - A);
    }
}

int main()
{
    int T;
    scanf("%d", &T);

    for (int ce = 1; ce <= T; ce++)
    {
        printf("Case #%d: ", ce);

        C.read();
        PA.read();
        SA.read();
        PB.read();

        GetAnglePoint(PA, SA, C);
        if (cmp(d - C.r) >= 0)
        {
            if (cmp(cross(PB - PA, SA)) == 0 && cmp(dot(PB - PA, SA)) > 0)
            {
                puts("Yes");
            }
            else
            {
                puts("No");
            }
            continue;
        }

        node N;
        if (cmp(dis(AngleA - PA) - dis(AngleB - PA)) < 0)
        {
            N = AngleA;
        }
        else
        {
            N = AngleB;
        }

        int flag = 0;
        if (cmp(cross(PA - PB, N - PB)) == 0 && cmp(dot(PA - PB, N - PB)) <= 0)
        {
            flag = 1;
        }

        node tmp = GetLine(PA, C.o, N);
        point PA2 = PA + 2 * (tmp - PA);
        speed SA2 = N - PA2;
        if (cmp(cross(PB - N, SA2)) == 0 && cmp(dot(PB - N, SA2)) <= 0)
        {
            flag = 1;
        }

        if (flag)
        {
            puts("Yes");
        }
        else
        {
            puts("No");
        }
    }

    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏书山有路勤为径

目标跟踪与定位——状态与定位

卡尔曼滤波器可以结合不准确的传感器测量和稍微不准确的运动预测,以获得比仅来自传感器读数或仅有关运动的任何更好估计位置。

2452
来自专栏marsggbo

Andrew Ng机器学习课程笔记--week9(下)(推荐系统&协同过滤)

本周内容较多,故分为上下两篇文章。 本文为下篇。 一、内容概要 1. Anomaly Detection Density Estimation Proble...

2437
来自专栏逍遥剑客的游戏开发

Reconstructing Position From Depth

1593
来自专栏PPV课数据科学社区

数据挖掘知识脉络与资源整理(九)–柱形图

? 柱形图 简介 英文:histogram或者column diagram 排列在工作表的列或行中的数据可以绘制到柱形图中。在柱形图中,通常沿水平轴组织类别,...

31210
来自专栏杨熹的专栏

从 0 到 1 走进 Kaggle

本文结构: kaggle 是什么 如何参赛 解决问题一般步骤 进一步: 如何探索数据 如何构造特征 提交结果 ---- kaggle 是什么? Kaggle ...

5138
来自专栏深度学习自然语言处理

【概率笔记】条件概率这样学才快啦

比如,一个上学期间整天鬼混的学沫,根本就不好好学习,对于他而言,选择题的四个选项ABCD被他选取的概率就为1/4。而对于大学霸来说,题题都会,那么他选取每一个选...

903
来自专栏WOLFRAM

五形相生

在三维欧氏空间里,有且仅有五种正多面体:正四面体、立方体、正八面体、正十二面体、正二十面体。一般介绍正多面体的文献中,只会强调立方体和正四面体互为对偶,正十二面...

1394
来自专栏量化投资与机器学习

【深入研究】使用RNN预测股票价格系列二

接昨天的 系列一(可点击查看) 在系列一的教程中,我们想继续有关股票价格预测的主题,并赋予在系列1中建立的具有对多个股票做出响应能力的RNN。 为了区分不同价格...

4038
来自专栏人工智能头条

从0到1走进 Kaggle

1223
来自专栏Code_iOS

OpenGL ES 2.0 (iOS)[04]:坐标空间 与 OpenGL ES 2 3D空间

第一次变换 模型变换(Model Transforms):就是指从模型空间转换到世界空间的过程

1642

扫码关注云+社区

领取腾讯云代金券