题解 UVA149 【Forests】
分析
事实上这道题并不难，学过高中几何的同学都完全可以做的出来，可能是大家都没看太懂题目吧？
算法的关键就在于如何判断两棵树是否相互遮挡。每棵树的坐标都为整数，树的宽度和眼睛坐标是给定的，通过这些数据就可以来判断遮挡了。请看下图（为方便描述，树的直径和眼睛点坐标可能与题目要求不符）：
圆圈代表树，所有直线的交点为眼睛坐标，显然两棵白色的树对于当前的眼睛坐标来说是没有相互遮挡的。题目要求树干与眼睛点形成的夹角不能小于0.01度。按树干为最细的0.1计算，(0.1/2)/sin(0.01)≈286.48。也就是说当树干直径为0.1时，树干的中心必须与眼睛相距286以上才会使得其夹角小于0.01度，但中间隔了286棵树还没有被挡住是不可能出现的事，因此这种情况可以忽略。那么就只需要判断两棵树干之间是否满足最小的角度了。在上图中，蓝色部分的角度就是两棵树干之间的夹角，设为a；黄色部分的角度分别为两棵树干与眼睛形成的夹角的一半，设为b1和b2；由蓝色线条围成的角度（两棵树干的中心到眼睛）设为c，很显然有a=c-b1-b2。如果两棵树相互遮挡，必有c-b1-b2<0。利用这一点就可以方便的做出判断了。c的角度可由两个边向量做内积来计算，b1和b2可由反三角函数来计算，都是非常简单的。
接下来的问题就是如何遍例了。跟据测算，离眼睛最远且能看到树木不会超过10，因此遍例超过20×20=400棵树是没有必要的。根据这一点可以写一个四重循环，对于每一棵树都把其它所有的树遍例一次，判断它是否被遮挡。然而离眼睛点近的树不可能被更远的树挡住，因此可以优化这个遍例的过程。如下图所示：
按照颜色由浅到深的顺序遍例，就可以减少大量多余的判断。显然浅灰色的一圈只需判断是否被白色的挡住，而深灰色的只需判断是否被白色和浅灰色的挡住。当然，还可以更加的优化，我们可以比较精确的计算出一棵树可能被里面的哪几棵树挡住，但这样做的代码会很长，对于解这道题来说是没有太大意义的（想冲击0秒的同学可以尝试）。
下面奉上本蒟蒻的代码
#include<bits/stdc++.h>
using namespace std;
//用于存储坐标的结构体
struct POINT{int x; int y;};
//主函数
int main(void) {
//dRad为180/pi，用于弧度到角度的转换，
const float fRad = 57.295779513082320876798154814105f;
//dMax为cos(0.01)，任何大于此值的参数都不能进行acos
const float fMax = 0.99999998476912904932780850903444f;
//循环处理每一组输入的数据，d为直径，x和y为观查者坐标
for (float d, x, y; cin >> d >> x >> y && d != 0; ) {
//将所有值放大100倍并取整，一可加快运算，二可保证精度
POINT Eye = {int(x * 100 + 0.5), int(y * 100 + 0.5)};
int nDiam = (int)(d * 100 + 0.5), nCnt = 0;
//依次由里圈向外层层遍例每棵树，检查是否被里面的树遮挡
for (int iBeg = 0, iEnd = 100; iEnd <= 1000;
iBeg -= 100, iEnd += 100) {
//遍例外面这一圈的树
for (int i = 0; i < iEnd - iBeg; i += 100) {
POINT Out[4] = {//一圈分别为左边、上边
{iBeg, iBeg + i}, {iBeg + i, iEnd},
//右边和下边
{iEnd, iEnd - i}, {iEnd - i, iBeg}};
//遍例四条边上的树
for (int j = 0; j < 4; j++) {
//遍例圈里面所有的树，In为树的坐标
POINT In = {iBeg + 100, iBeg + 100};
for (; In.y <= iEnd - 100; In.y += 100) {
for (In.x = iBeg + 100; In.x <= iEnd - 100;
In.x += 100) {//以下算法判定两棵树是否遮挡
//分别建立里面树和处面树与眼睛坐标的向量
POINT NVec = {In.x - Eye.x, In.y - Eye.y};
POINT FVec = {Out[j].x - Eye.x, Out[j].y - Eye.y};
//两个向量求内积
int nProd = NVec.x * FVec.x + NVec.y * FVec.y;
//求两个向量的模
float fNMod = sqrt((float)(NVec.x * NVec.x +
NVec.y * NVec.y));
float fFMod = sqrt((float)(FVec.x * FVec.x +
FVec.y * FVec.y));
//内积公式求夹角
float fACOS = nProd / (fNMod * fFMod);
if (fACOS >= fMax) { //夹角不能大于cos(0.01)
break;
}
//求出夹角角度
float fAng = acos(fACOS) * fRad;
//分别计算两棵树干自身与眼睛形成的的夹角
fNMod = asin((float)nDiam / 2.0f / fNMod) * fRad;
fFMod = asin((float)nDiam / 2.0f / fFMod) * fRad;
//判断是否遮挡，如果有则跳出循环
if (fAng - fNMod - fFMod <= 0.01f) {
break;
}
}
//未完成内循环，说明存在遮挡，继续向外跳出
if (In.x <= iEnd - 100) {
break;
}
}
//累计可见树的个数
nCnt += (In.y > iEnd - 100);
}
}
}
//输出结果
cout << nCnt << endl;
}
return 0;
}