首页 > ACM题库 > HDU-杭电 > HDU 4793-Collision-计算几何-[解题报告]HOJ
2015
09-18

HDU 4793-Collision-计算几何-[解题报告]HOJ

Collision

问题描述 :

There’s a round medal fixed on an ideal smooth table, Fancy is trying to throw some coins and make them slip towards the medal to collide. There’s also a round range which shares exact the same center as the round medal, and radius of the medal is strictly less than radius of the round range. Since that the round medal is fixed and the coin is a piece of solid metal, we can assume that energy of the coin will not lose, the coin will collide and then moving as reflect.
Now assume that the center of the round medal and the round range is origin ( Namely (0, 0) ) and the coin’s initial position is strictly outside the round range.
Given radius of the medal Rm, radius of coin r, radius of the round range R, initial position (x, y) and initial speed vector (vx, vy) of the coin, please calculate the total time that any part of the coin is inside the round range. Please note that the coin might not even touch the medal or slip through the round range.

输入:

There will be several test cases. Each test case contains 7 integers Rm, R, r, x, y, vx and vy in one line. Here 1 ≤ Rm < R ≤ 2000, 1 ≤ r ≤ 1000, R + r < |(x, y)| ≤ 20000, 1 ≤ |(vx, vy)| ≤ 100.

输出:

There will be several test cases. Each test case contains 7 integers Rm, R, r, x, y, vx and vy in one line. Here 1 ≤ Rm < R ≤ 2000, 1 ≤ r ≤ 1000, R + r < |(x, y)| ≤ 20000, 1 ≤ |(vx, vy)| ≤ 100.

样例输入:

5 20 1 0 100 0 -1
5 20 1 30 15 -1 0

样例输出:

30.000
29.394

给出一个圆形奖牌的半径和一个圆形区域的半径,还有一枚硬币的半径,然后桌面是光滑的,给出圆硬币的速度(大小和方向,vx,vy)和坐标(圆区域和圆奖牌同心且心作为源点),问硬币在圆区域滑动的时间是多少(任何一部分在圆区域都算),硬币碰到圆奖牌会反弹,能量不变(速度不变)

第一次做平面几何题

看了题解,题解的板子真好用

大概来说有三种情况,如下图

第一种是进入圆区而不碰撞,查看h和Rm+r的关系

第二种是进入圆区且碰撞,查看h和Rm+r的关系

第三种是不进入圆区,查看方向向量和圆心到初始点向量这两个向量的夹角还有h和R+r的关系,而且应该先看向量,也可以先看R+r再讨论向量

Collision

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#define PI acos(-1.0)
#define maxn 100005
#define INF 0x7fffffff
#define eps 1e-8
using namespace std;
int cmp(double x) {
	if(fabs(x)<eps)
		return 0;
	if(x>0)
		return 1;
	return -1;
}
inline int sgn(double n) {
	return fabs(n)<eps?0:(n<0?-1:1);
}
inline double sqr(double x) {
	return x*x;
}
struct point{
	double x,y;
	point() {}
	point(double a,double b):x(a),y(b) {}
	void input() {
		scanf("%lf%lf",&x,&y);
	}
	friend point operator + (const point &a,const point &b) {
		return point(a.x+b.x,a.y+b.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 cmp(a.x-b.x)==0 &&cmp(a.y-b.y)==0;
	}
	friend point operator * (const point &a,const double &b) {
		return point(a.x*b,a.y*b);
	}
	friend point operator * (const double &a,const point &b) {
		return point(a*b.x,a*b.y);
	}
	friend point operator / (const point &a,const double &b) {
		return point(a.x/b,a.y/b);
	}
	double norm() {
		return sqrt(sqr(x)+sqr(y));
	}//到原点距离
	void out () const {
		printf("%.2f %.2f",x,y);
	}
};
double det (const point &a,const point &b) {
	return a.x*b.y-a.y*b.x;
}//叉积
double dot (const point &a,const point &b) {
	return a.x*b.x+a.y*b.y;
}//点乘
double dist (const point &a,const point &b) {
	return (a-b).norm();
}//距离
point rotate_point(const point &p,double A) {
	double tx=p.x,ty=p.y;
	return point (tx*cos(A)-ty*sin(A),tx*sin(A)+ty*cos(A));
}//旋转,A是弧度
struct line {
	point a,b;
	line() {}
	line(point x,point y):a(x),b(y) {}
	point dire()const {
		return b-a;
	}//向量
	double len() {
		return dire().norm();
	}
};
bool parallel(line a,line b) {
	return !cmp(det(a.a-a.b,b.a-b.b));
}
bool line_make_point (line a,line b,point &res) {
	if(parallel(a,b))
		return false;
	double s1=det(a.a-b.a,b.b-b.a);
	double s2=det(a.b-b.a,b.b-b.a);
	res=(s1*a.b-s2*a.a)/(s1-s2);
	return true;
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("/home/rainto96/in.txt","r",stdin);
#endif
	double Rm,R,r,x,y,vx,vy;
	while(~scanf("%lf%lf%lf%lf%lf%lf%lf",&Rm,&R,&r,&x,&y,&vx,&vy)){
                point s=point(x,y);
                point dir=point(vx,vy);
                if(dot(s,dir)>=0){
                        printf("0.000\n");
                        continue;
                }
                point tmp=point(vy,-vx);
                line l1=line(point(0,0),tmp);
                line l2=line(s,point(s.x+vx,s.y+vy));
                point ans;
                line_make_point(l1,l2,ans);
                double h=ans.norm();
                double h1=R+r;
                double h2=Rm+r;
                double speed=sqrt(vx*vx+vy*vy);
                if(h>=h1){
                        printf("0.000\n");
                        continue;
                }
                if(h>=h2){
                        double time=sqrt(h1*h1-h*h)/speed*2;
                        printf("%f\n",time);
                        continue;
                }else{
                        double time=sqrt(h1*h1-h*h)-sqrt(h2*h2-h*h);
                        time=time/speed*2;
                        printf("%f\n",time);
                        continue;
                }
	}
	return 0;
}

参考:http://blog.csdn.net/u011775691/article/details/39372153