[HDU 5572] An Easy Physics Problem (点在线上判定+对称)

2024-06-21 19:38

本文主要是介绍[HDU 5572] An Easy Physics Problem (点在线上判定+对称),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

HDU - 5572

给定一个圆和圆外两个点 A和 B
现在有一个质点在 A处,有速度方向 V
其与圆的碰撞是弹性碰撞,问质点是否能经过 B


分情况讨论

  1. 如果射线不与圆相交,直接判定点是否在射线上
  2. 如果射线与圆相交,那么列方程解出与原交点
    并得出反弹的法线方程,然后以法线方程作对称
    最后判断点是否在一条线段和一条射线上

作对称的话可以将点 A以法线作对称,然后再用撞击点和对称点得到撞后轨迹

#pragma comment(linker, "/STACK:102400000,102400000")
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <string>
#include <complex>
using namespace std;
typedef pair<int,int> Pii;
typedef long long LL;
typedef unsigned long long ULL;
typedef double DBL;
typedef long double LDBL;
#define MST(a,b) memset(a,b,sizeof(a))
#define CLR(a) MST(a,0)
#define SQR(a) ((a)*(a))
#define PCUT puts("\n----------")const DBL eps = 1e-8;
int sgn(DBL x){return x<-eps?-1:(x>eps?1:0);}
struct Vector
{DBL x, y;Vector(DBL _x=0, DBL _y=0):x(_x),y(_y){}Vector operator + (const Vector &rhs) const {return Vector(x+rhs.x, y+rhs.y);}Vector operator - (const Vector &rhs) const {return Vector(x-rhs.x, y-rhs.y);}Vector operator * (const DBL &rhs) const {return Vector(x*rhs, y*rhs);}Vector operator / (const DBL &rhs) const {return Vector(x/rhs, y/rhs);}DBL operator * (const Vector &rhs) const {return x*rhs.x + y*rhs.y;}DBL operator ^ (const Vector &rhs) const {return x*rhs.y - y*rhs.x;}int read(){return scanf("%lf%lf", &x, &y);}int pri(){cout << x << " " << y << endl; return 0;}
};
typedef Vector Point;
struct Line
{Vector u,v,s;Line(){}Line(Point _u, Point _v):u(_u),v(_v),s(_v-_u){}
};struct Circle
{Point o; DBL r;Circle(){};void read(){o.read(); scanf("%lf", &r);}
};int N;
Point A, B, V;
Circle O;DBL Vlen(Vector);
Vector Normal(Vector);
Point SISC(Line,Circle);
bool PointOnHline(Point,Line);
bool PointOnSegment(Point,Line);
DBL PointToLine(Point,Line);int main()
{#ifdef LOCALfreopen("in.txt", "r", stdin);
//  freopen("out.txt", "w", stdout);#endifint T;scanf("%d", &T);for(int ck=1; ck<=T; ck++){O.read(); A.read(); V.read(); B.read();Line l1(A, A+V);DBL dist = PointToLine(O.o, l1);bool ok=0;if(sgn(dist-O.r)>=0 || sgn(V*(O.o-A))<=0) ok |= PointOnHline(B, l1);else{Line l2(O.o, SISC(l1,O));if(PointOnHline(O.o, l1)) ok |= PointOnHline(B, l2);else{Vector n = Normal(l2.s);if(sgn(n*V)<0) n=n*(-1);n = n/Vlen(n);ok |= PointOnSegment(B, Line(A, l2.v)) || PointOnHline(B, Line(l2.v, A+n*2*PointToLine(A, l2)));}}printf("Case #%d: %s\n", ck, ok?"Yes":"No");}return 0;
}DBL Vlen(Vector v) { return sqrt(SQR(v.x) + SQR(v.y));}
Vector Normal(Vector v) {return Vector(-v.y, v.x);}bool PointOnHline(Point p, Line l)
{Vector temp = p-l.u;return sgn(temp^l.s) == 0 && sgn(temp*l.s) >= 0;
}bool PointOnSegment(Point p, Line l)
{return sgn( (l.u-p)^(l.v-p) )==0 && sgn( (l.u-p)*(l.v-p) )<=0;
}DBL PointToLine(Point p, Line l)
{return abs((p-l.u)^l.s)/Vlen(l.s);
}Point SISC(Line L, Circle C)
{Vector ou = L.u-C.o, s=L.s;DBL a = SQR(s.x) + SQR(s.y);DBL b = 2*(ou*s);DBL c = SQR(ou.x) + SQR(ou.y) - SQR(C.r);DBL d = b*b - 4*a*c;DBL t = (-b-sqrt(d))/(a+a);return L.u + s*t;
}

这篇关于[HDU 5572] An Easy Physics Problem (点在线上判定+对称)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1082152

相关文章

水位雨量在线监测系统概述及应用介绍

在当今社会,随着科技的飞速发展,各种智能监测系统已成为保障公共安全、促进资源管理和环境保护的重要工具。其中,水位雨量在线监测系统作为自然灾害预警、水资源管理及水利工程运行的关键技术,其重要性不言而喻。 一、水位雨量在线监测系统的基本原理 水位雨量在线监测系统主要由数据采集单元、数据传输网络、数据处理中心及用户终端四大部分构成,形成了一个完整的闭环系统。 数据采集单元:这是系统的“眼睛”,

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

电力系统中的A类在线监测装置—APView400

随着电力系统的日益复杂和人们对电能质量要求的提高,电能质量在线监测装置在电力系统中得到广泛应用。目前,市场上的在线监测装置主要分为A类和B类两种类型,A类和B类在线监测装置主要区别在于应用场景、技术参数、通讯协议和扩展性。选择时应根据实际需求和应用场景综合考虑,并定期维护和校准。电能质量在线监测装置是用于实时监测电力系统中的电能质量参数的设备。 APView400电能质量A类在线监测装置以其多核

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

hdu 2093 考试排名(sscanf)

模拟题。 直接从教程里拉解析。 因为表格里的数据格式不统一。有时候有"()",有时候又没有。而它也不会给我们提示。 这种情况下,就只能它它们统一看作字符串来处理了。现在就请出我们的主角sscanf()! sscanf 语法: #include int sscanf( const char *buffer, const char *format, ... ); 函数sscanf()和

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码: #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s

hdu 1754 I Hate It(线段树,单点更新,区间最值)

题意是求一个线段中的最大数。 线段树的模板题,试用了一下交大的模板。效率有点略低。 代码: #include <stdio.h>#include <string.h>#define TREE_SIZE (1 << (20))//const int TREE_SIZE = 200000 + 10;int max(int a, int b){return a > b ? a :

hdu 1166 敌兵布阵(树状数组 or 线段树)

题意是求一个线段的和,在线段上可以进行加减的修改。 树状数组的模板题。 代码: #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while

uva 10025 The ? 1 ? 2 ? ... ? n = k problem(数学)

题意是    ?  1  ?  2  ?  ...  ?  n = k 式子中给k,? 处可以填 + 也可以填 - ,问最小满足条件的n。 e.g k = 12  - 1 + 2 + 3 + 4 + 5 + 6 - 7 = 12 with n = 7。 先给证明,令 S(n) = 1 + 2 + 3 + 4 + 5 + .... + n 暴搜n,搜出当 S(n) >=