1675.htm

总共80多道题的POJ详细解题报告

<h1 align="center">解题报告 Happy Birthday （POJ 1675）</h1> 
<p align="center">一道很简单的题</p>
<p align="left"><b>题目来源</b>：PKU有奖月赛II</p>
<p align="left"><b>作者 </b><font size="3">张法睿</font></p>
<p align="left"><b><font size="3">解法</font></b></p>
<p align="left"><font size="3">分别计算三个蜡烛的极角，分析三个蜡烛是否挤在一个扇形里面，</font></p>
<p align="left"><font size="3">是，则分不开，</font></p>
<p align="left"><font size="3">不是，则能分开。</font></p>
<p align="left"><b><font size="3">解体思路</font></b></p>
<p align="left">根据给出的蜡烛坐标，判断蛋糕可否等分为三个顶角为120度的扇形，且分后三根蜡烛分别在三个区域中</p>
<p align="left">仅要求判断能否划分，并不要求给出划分。</p>
<p align="left">不能分开的情况比较好判断，即三个蜡烛挤在一个扇形中</p>
<p align="left">否则必然能分开，如图：</p>
<p align="left">　<img src="1675.bmp" width="200" height="200"></p>
<p align="left">简单的考虑，只要判断蜡烛三与蜡烛一的角度茶就可以了。</p>
<p align="left">但是，由于在圆上360度与0度是重合的，所以蜡烛挤在一起共有三种可能的情况，</p>
<p align="left">每种情况下，坐标的判据略有不同（约定角度角度最小的蜡烛为蜡烛一，最大的为蜡烛三，中间的为蜡烛二）</p>
<p align="left">　</p>
<p align="left">　<img src="1675a.bmp" width="200" height="200">
<img src="1675b.bmp" width="200" height="200"> 
 　<img src="1675c.bmp" width="200" height="200">
<p align="left">如果不属于这三种情况之一，则必然能被分开</p>
<p align="left">最开始考虑过浮点误差，但第一个版本的程序没有为此进行优化，</p>
<p align="left">然后，也就那么过了，也就没再多想。</p>
<p align="left"><b>数据结构：</b>（无）</p>
<p align="left"><b>时空复杂度：</b>常数</p>
<p align="left"><b>源程序</b></p>
<pre>#include &lt;iostream&gt;
#include &lt;cmath&gt; <font color="#008000">//c的数学库</font>
using namespace std;


double getAngle(double x,double y)
<font color="#008000">//根据给定的坐标计算极角</font>
{
	double pi=3.14159265358979323846;
	double angle;
	double r=sqrt(x*x+y*y);
	if (y&gt;=0)
	{
		angle=acos(x/r);
	}
	else
	{
		angle=2*pi-acos(x/r);
	}
	angle=angle/pi*180;
	return angle;
}

void swap(double &amp;a,double &amp;b)
{
	double buf;
	buf=a;
	a=b;
	b=buf;
}


int main()
{
	double a1,a2,a3;
	int r,x1,y1,x2,y2,x3,y3;
	int t;
	cin&gt;&gt;t;
	while(t--)
	{
		cin&gt;&gt;r&gt;&gt;x1&gt;&gt;y1&gt;&gt;x2&gt;&gt;y2&gt;&gt;x3&gt;&gt;y3;
<font color="#008000">		//下面是计算三个极角</font>
		a1=getAngle(x1,y1);
		a2=getAngle(x2,y2);
		a3=getAngle(x3,y3);
		<font color="#008000">//下面是对三个蜡烛进行排序</font>
		if (a2&lt;a1) swap(a1,a2);
		if (a3&lt;a1) swap(a1,a3);
		if (a2&gt;a3) swap(a2,a3);
		if (a1&gt;a3) swap(a1,a3);
		bool ans;
		ans=true;
		<font color="#008000">//分别对三种挤在一起的情况做出判断</font>
		if (a3-a1&lt;=120) ans=false;
		if (a2+360-a3&lt;=120) ans=false;
		if (a1+360-a2&lt;=120) ans=false;
		if (ans) cout&lt;&lt;&quot;Yes&quot;&lt;&lt;endl;
		else cout&lt;&lt;&quot;No&quot;&lt;&lt;endl;
	}
}</pre>
<p align="left">　</p>
<p align="left">　</p>