HDU 5572 An Easy Physics Problem (计算几何+对称点模板)
HDU 5572 An Easy Physics Problem (计算几何)
题目链接http://acm.hdu.edu.cn/showproblem.php?pid=5572
Description
On an infinite smooth table, there's a big round fixed cylinder and a little ball whose volume can be ignored.
Currently the ball stands still at point A, then we'll give it an initial speed and a direction. If the ball hits the cylinder, it will bounce back with no energy losses.
We're just curious about whether the ball will pass point B after some time.
Input
First line contains an integer T, which indicates the number of test cases.
Every test case contains three lines.
The first line contains three integers Ox, Oy and r, indicating the center of cylinder is (Ox,Oy) and its radius is r.
The second line contains four integers Ax, Ay, Vx and Vy, indicating the coordinate of A is (Ax,Ay) and the initial direction vector is (Vx,Vy).
The last line contains two integers Bx and By, indicating the coordinate of point B is (Bx,By).
⋅ 1 ≤ T ≤ 100.
⋅ |Ox|,|Oy|≤ 1000.
⋅ 1 ≤ r ≤ 100.
⋅ |Ax|,|Ay|,|Bx|,|By|≤ 1000.
⋅ |Vx|,|Vy|≤ 1000.
⋅ Vx≠0 or Vy≠0.
⋅ both A and B are outside of the cylinder and they are not at same position.
Output
For every test case, you should output "Case #x: y", where x indicates the case number and counts from 1. y is "Yes" if the ball will pass point B after some time, otherwise y is "No".
Sample Input
2
0 0 1
2 2 0 1
-1 -1
0 0 1
-1 2 1 -1
1 2
Sample Output
Case #1: No
Case #2: Yes
题意:
在平面内给你一个固定的实心圆,然后从a点有一个球,给你运动方向问能否撞击到b点。
题解:
首先是能不能够撞击到大的圆。这个判断可以联立运动方程和圆的方程,产生一个一元二次方程,无解或者解小于0则是不撞击。如不能撞击到那么就判断直线运动能否撞击到b点即可。如果能撞击到,判断撞击之前能否撞到b点。如不能,将a点关于圆心与撞击点连成的直线的对称点求出,这样就可以再次判断。注意:一定不要通过普适方程求解,使用向量求解对称点,否则Wa到世界末日。
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
const ld eps = 1e-10;
ld r;
int sgn(ld x){
if (fabs(x) < eps)
return 0;
return x > 0?1:-1;
}
struct Point{
ld x,y;
Point (double _x = 0, double _y = 0):x(_x), y(_y) {}
bool operator < (const Point &b) const {
return (sgn (x-b.x) == 0 ? sgn (y-b.y) < 0 : x < b.x);
}
Point operator + (const Point &b) const {
return Point (x+b.x, y+b.y);
}
Point operator - (const Point &b) const {
return Point (x-b.x, y-b.y);
}
Point operator * (double a) {
return Point (x*a, y*a);
}
Point operator / (double a) {
return Point (x/a, y/a);
}
double len2 () {//返回长度的平方
return x*x + y*y;
}
double len () {//返回长度
return sqrt (len2 ());
}
Point change_len (double r) {//转化为长度为r的向量
double l = len ();
if (sgn (l) == 0) return *this;//零向量返回自身
r /= l;
return Point (x*r, y*r);
}
};
Point a,b,c,da;
bool rig(ld x,ld y,ld dx,ld dy,ld px,ld py)
{
ld t;
if (sgn(dx) == 0){
t = (py-y)/dy ;
if (sgn(x+t*dx-px) == 0 && t >= 0)
return true;
return false;
}else {
t = (px-x)/dx;
if (sgn(y+t*dy-py) == 0 && t >= 0)
return true;
return false;
}
}
ld dot(const Point &a,const Point &b){
return a.x*b.x+a.y*b.y;
}
Point projection (Point p, Point s,Point e) {
return s + (((e-s) * dot (e-s, p-s)) / (e-s).len2() );
}
Point dc(Point p,Point s,Point e)
{
Point q = projection(p,s,e);
return Point (2*q.x-p.x, 2*q.y-p.y);
}
bool solve()
{
ld A,B,C;
A = da.x*da.x + da.y*da.y;
B = 2.0*(da.x*(a.x-c.x) + da.y*(a.y-c.y)) ;
C = (a.x-c.x)*(a.x-c.x) + (a.y-c.y)*(a.y-c.y) -r*r;
ld dlt = B*B - 4.0*A*C;
if (sgn(dlt) <= 0){
return rig(a.x,a.y,da.x,da.y,b.x,b.y);
}else {
ld t = (-B-sqrt(dlt))/A/2.0;
if (sgn(t) < 0){
return rig(a.x,a.y,da.x,da.y,b.x,b.y);
}
Point hit;
hit.x = a.x+t*da.x;
hit.y = a.y+t*da.y;
if (rig(a.x,a.y,da.x,da.y,b.x,b.y))
if (b.x >= min(hit.x,a.x) && b.x <= max(hit.x,a.x) && b.y >= min(a.y,hit.y) && b.y <= max(a.y,hit.y))
return true;
Point bb = dc(a,hit,c);
return rig(hit.x,hit.y,bb.x-hit.x,bb.y-hit.y,b.x,b.y);
}
}
int main()
{
int t;
scanf("%d",&t);
for (int _t = 1; _t <= t; _t++){
cin>>c.x>>c.y>>r;
cin>>a.x>>a.y>>da.x>>da.y;
cin>>b.x>>b.y;
printf("Case #%d: ",_t);
if (solve())
printf("Yes\n");
else printf("No\n");
}
return 0;
}
最新文章
- position absolute 绝对定位 设置问题
- JAVA(3)
- SIGABRT的可能原因
- 文件系统权限引起IIS站点总跳登录页面
- node js学习(二)——REPL(交互式解释器)
- IE6下div层被select控件遮住的问题解决方法
- nyoj 284 坦克大战 简单搜索
- iOS 中constraint 不等于约束和低优先级约束使用的简单体会
- MySQL学习笔记_2_MySQL创建数据表(上)
- 什么是RAID
- 你自认为理解了JavaScript?
- 【Qt】Qt Assistant介绍【转】
- VB几种函数参数传递方法,Variant,数组,Optional,ParamArray
- Selenium各种工具比较
- Docker 入门之swarm部署web应用
- python使用urllib2 http 下载参数的try catch
- H5 video标签的属性
- 树莓派Raspberry Pi zero w无线联网实测
- 2017-2018-2 1723《程序设计与数据结构》第三周作业 &; 实验一 总结
- ElasticSearch5.0——IK词库加载
热门文章
题目链接http://acm.hdu.edu.cn/showproblem.php?pid=5572
Description
On an infinite smooth table, there's a big round fixed cylinder and a little ball whose volume can be ignored.
Currently the ball stands still at point A, then we'll give it an initial speed and a direction. If the ball hits the cylinder, it will bounce back with no energy losses.
We're just curious about whether the ball will pass point B after some time.
Input
First line contains an integer T, which indicates the number of test cases.
Every test case contains three lines.
The first line contains three integers Ox, Oy and r, indicating the center of cylinder is (Ox,Oy) and its radius is r.
The second line contains four integers Ax, Ay, Vx and Vy, indicating the coordinate of A is (Ax,Ay) and the initial direction vector is (Vx,Vy).
The last line contains two integers Bx and By, indicating the coordinate of point B is (Bx,By).
⋅ 1 ≤ T ≤ 100.
⋅ |Ox|,|Oy|≤ 1000.
⋅ 1 ≤ r ≤ 100.
⋅ |Ax|,|Ay|,|Bx|,|By|≤ 1000.
⋅ |Vx|,|Vy|≤ 1000.
⋅ Vx≠0 or Vy≠0.
⋅ both A and B are outside of the cylinder and they are not at same position.
Output
For every test case, you should output "Case #x: y", where x indicates the case number and counts from 1. y is "Yes" if the ball will pass point B after some time, otherwise y is "No".
Sample Input
2
0 0 1
2 2 0 1
-1 -1
0 0 1
-1 2 1 -1
1 2
Sample Output
Case #1: No
Case #2: Yes
题意:
在平面内给你一个固定的实心圆,然后从a点有一个球,给你运动方向问能否撞击到b点。
题解:
首先是能不能够撞击到大的圆。这个判断可以联立运动方程和圆的方程,产生一个一元二次方程,无解或者解小于0则是不撞击。如不能撞击到那么就判断直线运动能否撞击到b点即可。如果能撞击到,判断撞击之前能否撞到b点。如不能,将a点关于圆心与撞击点连成的直线的对称点求出,这样就可以再次判断。注意:一定不要通过普适方程求解,使用向量求解对称点,否则Wa到世界末日。
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
const ld eps = 1e-10;
ld r;
int sgn(ld x){
if (fabs(x) < eps)
return 0;
return x > 0?1:-1;
}
struct Point{
ld x,y;
Point (double _x = 0, double _y = 0):x(_x), y(_y) {}
bool operator < (const Point &b) const {
return (sgn (x-b.x) == 0 ? sgn (y-b.y) < 0 : x < b.x);
}
Point operator + (const Point &b) const {
return Point (x+b.x, y+b.y);
}
Point operator - (const Point &b) const {
return Point (x-b.x, y-b.y);
}
Point operator * (double a) {
return Point (x*a, y*a);
}
Point operator / (double a) {
return Point (x/a, y/a);
}
double len2 () {//返回长度的平方
return x*x + y*y;
}
double len () {//返回长度
return sqrt (len2 ());
}
Point change_len (double r) {//转化为长度为r的向量
double l = len ();
if (sgn (l) == 0) return *this;//零向量返回自身
r /= l;
return Point (x*r, y*r);
}
};
Point a,b,c,da;
bool rig(ld x,ld y,ld dx,ld dy,ld px,ld py)
{
ld t;
if (sgn(dx) == 0){
t = (py-y)/dy ;
if (sgn(x+t*dx-px) == 0 && t >= 0)
return true;
return false;
}else {
t = (px-x)/dx;
if (sgn(y+t*dy-py) == 0 && t >= 0)
return true;
return false;
}
}
ld dot(const Point &a,const Point &b){
return a.x*b.x+a.y*b.y;
}
Point projection (Point p, Point s,Point e) {
return s + (((e-s) * dot (e-s, p-s)) / (e-s).len2() );
}
Point dc(Point p,Point s,Point e)
{
Point q = projection(p,s,e);
return Point (2*q.x-p.x, 2*q.y-p.y);
}
bool solve()
{
ld A,B,C;
A = da.x*da.x + da.y*da.y;
B = 2.0*(da.x*(a.x-c.x) + da.y*(a.y-c.y)) ;
C = (a.x-c.x)*(a.x-c.x) + (a.y-c.y)*(a.y-c.y) -r*r;
ld dlt = B*B - 4.0*A*C;
if (sgn(dlt) <= 0){
return rig(a.x,a.y,da.x,da.y,b.x,b.y);
}else {
ld t = (-B-sqrt(dlt))/A/2.0;
if (sgn(t) < 0){
return rig(a.x,a.y,da.x,da.y,b.x,b.y);
}
Point hit;
hit.x = a.x+t*da.x;
hit.y = a.y+t*da.y;
if (rig(a.x,a.y,da.x,da.y,b.x,b.y))
if (b.x >= min(hit.x,a.x) && b.x <= max(hit.x,a.x) && b.y >= min(a.y,hit.y) && b.y <= max(a.y,hit.y))
return true;
Point bb = dc(a,hit,c);
return rig(hit.x,hit.y,bb.x-hit.x,bb.y-hit.y,b.x,b.y);
}
}
int main()
{
int t;
scanf("%d",&t);
for (int _t = 1; _t <= t; _t++){
cin>>c.x>>c.y>>r;
cin>>a.x>>a.y>>da.x>>da.y;
cin>>b.x>>b.y;
printf("Case #%d: ",_t);
if (solve())
printf("Yes\n");
else printf("No\n");
}
return 0;
}