首页 > 代码库 > HDU 1006 Tick and Tick 解不等式解法

HDU 1006 Tick and Tick 解不等式解法

一开始思考的时候觉得好难的题目,因为感觉很多情况,不知道从何入手。

想通了就不难了。

可以转化为一个利用速度建立不等式,然后解不等式的问题。

建立速度,路程,时间的模型如下:

/***************************************************************************
*								  *
*	秒钟的速度s=6°/s,分针是1/10°/s,时针是1/120°/s			  *
*	所以相对速度s_m=59/10°/s,s_h=719/120°/s,m_h=120/11°/s		  *
*	所以相差一度所需要的时间sm=10/59 s/°,sh=120/719 s/°,mh=120/11 s/°   *
*	他们差360°的周期为tsm=3600/59 s,tsh=43200/719 s,tmh=43200/11 s	  *
*	需要相差的角度为n。                                                          *
*	rsm>n → n*sm+k1*tsm < t < tsm-n*sm+k1*tsm;			  *
*	rsh>n → n*sh+k2*tsh < t < tsh-n*sh+k2*tsh;		           *
*	rmh>n → n*mh+k3*tmh < t < tmh-n*mh+k3*tmh;			  *
*	三个条件都满足所占的总时间即为时针、分针、秒针相差角度大于n的总时间          *
*								  *
***************************************************************************/

以上内容出处: http://acm.hdu.edu.cn/discuss/problem/post/reply.php?postid=4499&messageid=1&deep=0


就是利用中学的公式了:物体1的速度是V1,物体2的速度是V2,那么经过一段时间t,他们的距离差S = V1*t - V2*t

这里的物体就是时针,分针, 秒针,然后就建模成这样一个简单的物理模型。能把这个模型建立起来,一切就解决了。

当然,这也是最难的地方。


参考一下这个博客:http://www.cnblogs.com/kuangbin/archive/2011/12/04/2275470.html


下面是我的代码:

#include <algorithm>
#include <cstdio>
#include <utility>
using namespace std;

class TickAndTick_1
{
	void intersectRange(pair<double, double> &rs, 
		pair<double, double> &a, pair<double, double> &b)
	{
		rs.first = max(a.first, b.first);
		rs.second = min(a.second, b.second);
		if (rs.first > rs.second) rs.first = rs.second = 0.0;
	}

	void solveInequality(double a, double b, double D, pair<double, double> &rs)
	{
		if (a == 0.0) return;

		pair<double, double> pa;
		if (a < 0.0)
		{
			pa.first = (360.0-b-D) / a;
			pa.second = (D-b) / a;
		}
		else
		{
			pa.first = (D-b) / a;
			pa.second = (360.0-b-D) / a;
		}
		pair<double, double> sixty(0.0, 60.0);
		intersectRange(rs, pa, sixty);
	}

	double happyInMinute(int h, int m, double D)
	{
		pair<double, double> pas[3][2];

		double a = 1.0 / 120.0 - 0.1;  
		double b = 30.0 * h + m/2.0 - 6.0*m; 
		solveInequality(a, b, D, pas[0][0]);
		solveInequality(-a, -b, D, pas[0][1]);

		a = 1.0/120 - 6.0;
		b = 30*h + m/2.0;
		solveInequality(a, b, D, pas[1][0]);
		solveInequality(-a, -b, D, pas[1][1]);

		a = 0.1 - 6;
		b = 6 * m;
		solveInequality(a, b, D, pas[2][0]);
		solveInequality(-a, -b, D, pas[2][1]);

		double ans = 0.0;
		pair<double, double> tmp_1, tmp_2;
		for (int i = 0; i < 2; i++)
		{
			for (int j = 0; j < 2; j++)
			{
				intersectRange(tmp_1, pas[0][i], pas[1][j]);

				intersectRange(tmp_2, tmp_1, pas[2][0]);
				ans += tmp_2.second - tmp_2.first;

				intersectRange(tmp_2, tmp_1, pas[2][1]);
				ans += tmp_2.second - tmp_2.first;
			}
		}
		return ans;
	}

public:
	TickAndTick_1()
	{
		double D;
		while(scanf("%lf",&D) && -1 != D)
		{
			double ans = 0.0;
			int h, m;
			for (h = 0; h < 12; h++)
			{
				for(m = 0; m < 60; m++)
				{
					ans += happyInMinute(h, m, D);
				}    
			}    
			printf("%.3lf\n",ans * 100.0 / (60.0 * 60.0 * 12.0));    
		}    
	}
};