[编程题] 寻找三角形
时间限制：1秒
空间限制：32768K
三维空间中有N个点，每个点可能是三种颜色的其中之一，三种颜色分别是红绿蓝，分别用'R', 'G', 'B'表示。
现在要找出三个点，并组成一个三角形，使得这个三角形的面积最大。
但是三角形必须满足：三个点的颜色要么全部相同，要么全部不同。
输入描述:
首先输入一个正整数N三维坐标系内的点的个数.(N <= 50)
接下来N行，每一行输入 c x y z，c为'R', 'G', 'B' 的其中一个。x，y，z是该点的坐标。(坐标均是0到999之间的整数)
输出描述:
输出一个数表示最大的三角形面积，保留5位小数。
输入例子:
5 R 0 0 0 R 0 4 0 R 0 0 3 G 92 14 7 G 12 16 8
输出例子:
6.00000
解题思路：本题先定义一个计算三维空间三角形面积的函数
1）定义结构体，存储每个点的信息
2）遍历所有点，选取三个，求出面积
3）求出面积后比较三个点的颜色全部相同或者全部不同，如果满足，且面积大于之前的最大面积，更新最大面积
4）按要求输入小数点后五位
1 #include <iostream> 2 #include <cmath> 3 #include"iomanip" 4 5 using namespace std; 6 7 struct Point 8 { 9 char color; 10 int x; 11 int y; 12 int z; 13 }; 14 //求三角形面积; 15 //返回-1为不能组成三角形; 16 double count_triangle_area(Point a,Point b,Point c){ 17 double area = -1; 18 19 double side[3];//存储三条边的长度; 20 21 side[0] = sqrt(pow(a.x - b.x,2)+pow(a.y - b.y,2) + pow(a.z - b.z,2)); 22 side[1] = sqrt(pow(a.x - c.x,2)+pow(a.y - c.y,2) + pow(a.z - c.z,2)); 23 side[2] = sqrt(pow(c.x - b.x,2)+pow(c.y - b.y,2) + pow(c.z - b.z,2)); 24 25 //不能构成三角形; 26 if(side[0]+side[1]<=side[2] || side[0]+side[2]<=side[1] || side[1]+side[2]<=side[0]) return area; 27 28 //利用海伦公式。s=sqr(p*(p-a)(p-b)(p-c)); 29 double p = (side[0]+side[1]+side[2])/2; //半周长; 30 area = sqrt(p*(p-side[0])*(p-side[1])*(p-side[2])); 31 32 return area; 33 } 34 int main() 35 { 36 int n; 37 while(cin>>n) 38 { 39 double area = 0.0; 40 double max_area = 0.0; 41 Point p[n]; 42 for(int i=0;i<n;i++) 43 { 44 cin>>p[i].color>>p[i].x>>p[i].y>>p[i].z; 45 } 46 for(int i=0;i<n;i++) 47 { 48 for(int j=i+1;j<n;j++) 49 { 50 for(int k=j+1;k<n;k++) 51 { 52 area = count_triangle_area(p[i],p[j],p[k]); 53 if(((p[i].color == p[j].color) && (p[i].color == p[k].color)) 54 ||((p[i].color != p[j].color)&&(p[i].color != p[k].color)&&(p[j].color != p[k].color))) 55 { 56 max_area = max(max_area,area); 57 } 58 } 59 } 60 } 61 cout.setf(ios::fixed);//位数不够自动补0（若需要自动补0，在cout之前进行补0的定义，cout中加入“<<fixed”） 62 cout << fixed <<setprecision(5)<<max_area<<endl; 63 } 64 return 0; 65 }