2014
01-10

# UVa-194-Triangle(三角形)计算几何

Time limit: 30.000 seconds

## Problem问题

A triangle is a basic shape of planar geometry. It consists of three straight lines and three angles in between. Figure 1 shows how the sides and angles are usually labeled.

Figure: Triangle

A look into a book about geometry shows that many formulas for triangles exist:

The values of a, b, c, tex2html_wrap_inline64 , tex2html_wrap_inline66 , and tex2html_wrap_inline68 form a set of six parameters that fully define a triangle. If a large enough subset of these parameters is given, the missing ones can be calculated by using the formulas above.

You are to write a program that calculates the missing parameters for a given subset of the six parameters of a triangle. For some sets of parameters, it is not possible to calculate the triangle because either too few is known about the triangle or the parameters would lead to an invalid triangle. The sides of a valid triangle are greater than 0 and the angles are greater than 0 and less than tex2html_wrap_inline70 . Your program should detect this case and output: “Invalid input.” The same phrase should be output if more than the minimal set needed to compute the triangle is given but the parameters conflict with each other, e.g. all three angles are given but their sum is greater than tex2html_wrap_inline70 .

Other sets of parameters can lead to more than one but still a finite number of valid solutions for the triangle. In such a case, your program should output: “More than one solution.”

In all other cases, your program should compute the missing parameters and output all six parameters.

## Input输入

The first line of the input file contains a number indicating the number of parameter sets to follow. Each following line consists of six numbers, separated by a single blank character. The numbers are the values for the parameters a, tex2html_wrap_inline64 , b, tex2html_wrap_inline66 , c, and tex2html_wrap_inline68 respectively. The parameters are labeled as shown in figure 1. A value of -1 indicates that the corresponding parameter is undefined and has to be calculated. All floating-point numbers include at least eight significant digits.

## Output输出

Your program should output a line for each set of parameters found in the input file. If a unique solution for a valid triangle can be found for the given parameters, your program should output the six parameters a, tex2html_wrap_inline64 , b, tex2html_wrap_inline66 , c, tex2html_wrap_inline68 , separated by a blank character. Otherwise the line should contain the phrase

“More than one solution.” or

“Invalid input.”

as explained above.

The numbers in the output file should include at least six significant digits. Your calculations should be precise enough to get the six most significant digits correct (i.e. a relative error of 0.000001 is allowed).

## Sample input示例输入

4
47.9337906847 0.6543010109 78.4455517579 1.4813893731 66.5243757656 1.0059022695
62.72048064 2.26853639 -1.00000000 0.56794657 -1.00000000 -1.00000000
15.69326944 0.24714213 -1.00000000 1.80433105 66.04067877 -1.00000000
72.83685175 1.04409241 -1.00000000 -1.00000000 -1.00000000 -1.00000000

## Sample output示例输出

47.933791 0.654301 78.445552 1.481389 66.524376 1.005902
62.720481 2.268536 44.026687 0.567947 24.587225 0.305110
Invalid input.
Invalid input.

## Analysis分析

PI减两角得第三角：PIANGLE，p[nr]= -p[n1]-p[n2]

ASA：PIANGLE(5, 1, 3, 0), SINSIDE(0, 4, 1, 5), SINSIDE(2, 4, 3, 5)

AAS：PIANGLE(5, 1, 3, 0), SINSIDE(2, 0, 3, 1), SINSIDE(4, 0, 5, 1)

SAA：PIANGLE(3, 1, 5, 0), SINSIDE(2, 0, 3, 1), SINSIDE(4, 0, 5, 1)

SAS：COSSIDE(4, 0, 2, 5), COSANGLE(1, 2, 4, 0), COSANGLE(3, 0, 4, 2)

SSS：COSANGLE(1, 2, 4, 0), COSANGLE(3, 0, 4, 2), COSANGLE(5, 0, 2, 4)

SSA：SINANGLE(3, 2, 1, 0), PIANGLE(5, 1, 3, 0), SINSIDE(4, 0, 5, 1)

ASS：SINANGLE(5, 4, 1, 0), PIANGLE(3, 1, 5, 0), SINSIDE(2, 0, 3, 1)

## Solution解答

#include <iomanip>
#include <iostream>
#include <vector>
#include <map>
#include <cmath>

typedef unsigned char uchar;
enum TRIFUNC{PIANGLE, SINSIDE, SINANGLE, COSSIDE, COSANGLE};
enum TRITYPE{NA, AAA, ASA, AAS, SAA, SAS, SSS, SSA, ASS};
const double dPi =	3.14159265358979323846, dPi2 =	dPi / 2.0;
//与base的映射序号表
const int orderAry[3][6] = {
{0, 1, 2, 3, 4, 5}, {4, 5, 0, 1, 2, 3}, {2, 3, 4, 5, 0, 1},
};
//一行对应于一种TRITYPE，从ASA到ASS。一行中每5个为一子组，每一子组为TriFunc的后5个调用参数。
const int idxAry[][15] = { //数据参见文档
{PIANGLE, 5, 1, 3, 0, SINSIDE, 0, 4, 1, 5, SINSIDE, 2, 4, 3, 5},
{PIANGLE, 5, 1, 3, 0, SINSIDE, 2, 0, 3, 1, SINSIDE, 4, 0, 5, 1},
{PIANGLE, 3, 1, 5, 0, SINSIDE, 2, 0, 3, 1, SINSIDE, 4, 0, 5, 1},
{COSSIDE, 4, 0, 2, 5, COSANGLE, 1, 2, 4, 0, COSANGLE, 3, 0, 4, 2},
{COSANGLE, 1, 2, 4, 0, COSANGLE, 3, 0, 4, 2, COSANGLE, 5, 0, 2, 4},
{SINANGLE, 3, 2, 1, 0, PIANGLE, 5, 1, 3, 0, SINSIDE, 4, 0, 5, 1},
{SINANGLE, 5, 4, 1, 0, PIANGLE, 3, 1, 5, 0, SINSIDE, 2, 0, 3, 1},
};
//包括五种三角函数，从给定参数表中的某几个值（指定序号）计算出另一个值（指定序号）
void TriFunc(double *p, TRIFUNC fn, size_t nr, size_t n1, size_t n2, size_t n3)
{
switch (fn)
{
// PI减两角得第三角
case PIANGLE: p[nr] = dPi - p[n1] - p[n2]; break;
// 正弦定理求边
case SINSIDE: p[nr] = p[n1] * sin(p[n2]) / sin(p[n3]); break;
// 正弦定理求角
case SINANGLE: p[nr] = asin(p[n1] * sin(p[n2]) / p[n3]); break;
// 余弦定理求边
case COSSIDE: p[nr] = sqrt(p[n1] * p[n1] + p[n2] * p[n2] -
2 * p[n1] * p[n2] * cos(p[n3])); break;
// 余弦定理求角
case COSANGLE: p[nr] = acos((p[n1] * p[n1] + p[n2] * p[n2] -
p[n3] * p[n3]) / (2 * p[n1] * p[n2])); break;
}
}
// 检测三边长度是否合法
int CheckSides(double *p)
{
return (p[0] >= p[2] + p[4] || p[2] >= p[0] + p[4] ||
p[4] >= p[2] + p[0]);
}
// 检测边边角类型是否可以计算出唯一解
int CheckSSA(double *p, size_t nIdx1, size_t nIdx2, size_t nIdx3)
{
if (p[nIdx2] >= dPi || (p[nIdx2] >= dPi2 && p[nIdx1] < p[nIdx3]))
return 1;
if (p[nIdx2] < dPi2) {
double dTmp = sin(p[nIdx2]) * p[nIdx3];
if (p[nIdx1] < dTmp - 1e-15) return 1;
if (p[nIdx1] > dTmp + 1e-15 && p[nIdx1] < p[nIdx3]) return 2;
}
return 0;
}
// 检测所给三角形的参数是否非法
int Checker(TRITYPE type, double *pParams)
{
switch (type)
{
case AAA: return 1; // AAA类型为非法
case ASA: return (pParams[1] + pParams[3] >= dPi); //检测给定两角和是否大于PI
case AAS: return (pParams[1] + pParams[3] >= dPi); //检测给定两角和是否大于PI
case SAA: return (pParams[1] + pParams[5] >= dPi); //检测给定两角和是否大于PI
case SAS: return (pParams[5] >= dPi); //检测给定角是否大于PI
case SSA: return CheckSSA(pParams, 0, 1, 2); //专用函数检测
case ASS: return CheckSSA(pParams, 0, 1, 4); //专用函数检测
case SSS: return CheckSides(pParams); //检测三边是否合法
}
}

int main(void)
{
//求解器数据初始化，数据参见文档
std::map<uchar, TRITYPE> solvers;
solvers[21] = AAA; solvers[22] = ASA; solvers[52] = AAS; solvers[49] = SAA;
solvers[41] = SAS; solvers[42] = SSS; solvers[56] = SSA; solvers[50] = ASS;
solvers[23] = ASA; solvers[60] = AAS; solvers[54] = ASA; solvers[30] = ASA;
solvers[58] = SSS; solvers[31] = ASA; solvers[62] = SSS; solvers[63] = ASA;

//设定输出精度，保留6位小数
std::cout.precision(6);
size_t nLines = 0;
for (std::cin >> nLines; nLines > 0; --nLines) {
double params[6], tmpParams[6];
uchar nParamCnt = 0, cFlags = 0;
for (size_t j = 0; j < 6; ++j) { //录入一行6个参数
std::cin >> params[j];
if (params[j] <= 0 && params[j] != -1.0) {
nParamCnt = 0; //若参数为负但不为-1则判定参数非法
break;
}
else if(params[j] > 0) { //用cFlags表示有效参数的位置
cFlags |= (1 << (5 - j));
++nParamCnt;
}
}
if (nParamCnt < 3) { //如果参数数量小于3则判定参数非法
std::cout << "Invalid input." << std::endl;
continue;
}
int *pOrder = (int*)&orderAry[0][0];
TRITYPE type = solvers[cFlags];
//查找该有效参数位置属于哪一个base类型，pOrder为其与所属base的映射
for (; type == NA; pOrder += 6) {
cFlags = ((cFlags & 0x03) << 4) | (cFlags >> 2);
type = solvers[cFlags];
}
//排序为base要求的顺序（旋转三角形）
for (int i = 0; i < 6; ++i) tmpParams[i] = params[pOrder[i]];
int nr = Checker(type, tmpParams); //检测输入数据是否合法
if (nr == 0) { // 0为合法，1为非法，2为多解
for (size_t i = 0; i < 3; ++i) { //求解未知的三个参数
const int *p = &idxAry[type - 2][i * 5];
TriFunc(tmpParams, TRIFUNC(p[0]), p[1], p[2], p[3], p[4]);
}
for (int i = 0; i < 6 && nr == 0; ++i) { //验证求解的解果与输入是否对应
double dTmp = tmpParams[i];
if ((cFlags & (1 << (5 - i))) == 0) params[pOrder[i]] = dTmp;
else if (std::abs(params[pOrder[i]] - dTmp) > 1e-7) nr = 1;
}
}
if (nr == 0) //按要求格式输出计算的结果
for (int i = 0; i < 6; ++i)
std::cout << std::fixed << params[i] << (i == 5 ? "\n" : " ");
else if (nr == 1) std::cout << "Invalid input." << std::endl;
else std::cout << "More than one solution." << std::endl;
}
return 0;
}

1. 飞机某高度的最大爬升率是在特定速度和仰角下实现的，不同飞机达成最大爬升率的速度和角度是不一样的，不同情况下的sep爬升率也是不一样的，更不用说有些数据是海平面最大瞬时爬升率，这基本上没有实际意义了

2. 飞机某高度的最大爬升率是在特定速度和仰角下实现的，不同飞机达成最大爬升率的速度和角度是不一样的，不同情况下的sep爬升率也是不一样的，更不用说有些数据是海平面最大瞬时爬升率，这基本上没有实际意义了

3. 飞机某高度的最大爬升率是在特定速度和仰角下实现的，不同飞机达成最大爬升率的速度和角度是不一样的，不同情况下的sep爬升率也是不一样的，更不用说有些数据是海平面最大瞬时爬升率，这基本上没有实际意义了

4. 飞机某高度的最大爬升率是在特定速度和仰角下实现的，不同飞机达成最大爬升率的速度和角度是不一样的，不同情况下的sep爬升率也是不一样的，更不用说有些数据是海平面最大瞬时爬升率，这基本上没有实际意义了

5. 飞机某高度的最大爬升率是在特定速度和仰角下实现的，不同飞机达成最大爬升率的速度和角度是不一样的，不同情况下的sep爬升率也是不一样的，更不用说有些数据是海平面最大瞬时爬升率，这基本上没有实际意义了

6. 飞机某高度的最大爬升率是在特定速度和仰角下实现的，不同飞机达成最大爬升率的速度和角度是不一样的，不同情况下的sep爬升率也是不一样的，更不用说有些数据是海平面最大瞬时爬升率，这基本上没有实际意义了

7. 飞机某高度的最大爬升率是在特定速度和仰角下实现的，不同飞机达成最大爬升率的速度和角度是不一样的，不同情况下的sep爬升率也是不一样的，更不用说有些数据是海平面最大瞬时爬升率，这基本上没有实际意义了

8. 飞机某高度的最大爬升率是在特定速度和仰角下实现的，不同飞机达成最大爬升率的速度和角度是不一样的，不同情况下的sep爬升率也是不一样的，更不用说有些数据是海平面最大瞬时爬升率，这基本上没有实际意义了

9. 飞机某高度的最大爬升率是在特定速度和仰角下实现的，不同飞机达成最大爬升率的速度和角度是不一样的，不同情况下的sep爬升率也是不一样的，更不用说有些数据是海平面最大瞬时爬升率，这基本上没有实际意义了

10. 飞机某高度的最大爬升率是在特定速度和仰角下实现的，不同飞机达成最大爬升率的速度和角度是不一样的，不同情况下的sep爬升率也是不一样的，更不用说有些数据是海平面最大瞬时爬升率，这基本上没有实际意义了

11. 飞机某高度的最大爬升率是在特定速度和仰角下实现的，不同飞机达成最大爬升率的速度和角度是不一样的，不同情况下的sep爬升率也是不一样的，更不用说有些数据是海平面最大瞬时爬升率，这基本上没有实际意义了

12. #!/usr/bin/env python
def cou(n):
arr =
i = 1
while(i<n):
arr.append(arr[i-1]+selfcount(i))
i+=1
return arr[n-1]

def selfcount(n):
count = 0
while(n):
if n%10 == 1:
count += 1
n /= 10
return count