笔试刷题-百度2018-06-19

题目描述：

/**
三维空间中有N个点，每个点可能是三种颜色的其中之一，三种颜色分别是红绿蓝，
分别用'R', 'G', 'B'表示。
现在要找出三个点，并组成一个三角形，使得这个三角形的面积最大。
但是三角形必须满足：三个点的颜色要么全部相同，要么全部不同。
输入描述:
首先输入一个正整数N三维坐标系内的点的个数.(N <= 50)

接下来N行，每一行输入 c x y z，c为'R', 'G', 'B' 的其中一个。x，y，z是该点的坐标。
(坐标均是0到999之间的整数)


输出描述:
输出一个数表示最大的三角形面积，保留5位小数。

输入例子1:
5
R 0 0 0
R 0 4 0
R 0 0 3
G 92 14 7
G 12 16 8

输出例子1:
6.00000
*/ 

思路如下：

把点按颜色分组，然后遍历组内三角形和组间三角形
判断3点是否共线 等价于 判断3点是否能组成三角形

三角形面积向量叉积 的行列式公式即可（没加判断顺时针还是逆时针，所以要加绝对值即可）

代码如下：

#include<stdio.h>
#include<iostream>
#include<vector>
#include<cmath>

using namespace std;

struct Point{
    int x, y, z;
    Point(){}
    Point(int x, int y, int z){
        this->x=x;
        this->y=y;
        this->z=z;
    }
    Point(const Point& point){
        this->x=point.x;
        this->y=point.y;
        this->z=point.z;
    }
};

double NormSquare(vector<double> vec){
    int dim=vec.size();
    double normSquare=0;
    for(int i=0; i<dim; i++)
        normSquare+=(vec[i]*vec[i]);
    return normSquare;
}

double DotProduct(vector<double> vec1, vector<double> vec2){
    if(vec1.size()!=vec2.size())
        return -1;
    int dim=vec1.size();
    double dotProduct=0;
    for(int i=0; i<dim; i++)
        dotProduct+=(vec1[i]*vec2[i]);
    return dotProduct;
}

//vec1与vec2同维度
double CrossProductSquare(vector<double> vec1, vector<double> vec2){
    if(vec1.size()!=vec2.size())
        return -1;
    double crossProductSquare=0;
    crossProductSquare=NormSquare(vec1)*NormSquare(vec2)-DotProduct(vec1, vec2)*DotProduct(vec1, vec2);
    return crossProductSquare;
}

/**以下计算面积的方法选用叉积公式计算即可*/
double GetAreaSquare(Point p1, Point p2, Point p3){
    vector<double> vec1, vec2;
    vec1.push_back(1.0*(p1.x-p2.x));
    vec1.push_back(1.0*(p1.y-p2.y));
    vec1.push_back(1.0*(p1.z-p2.z));
    vec2.push_back(1.0*(p3.x-p2.x));
    vec2.push_back(1.0*(p3.y-p2.y));
    vec2.push_back(1.0*(p3.z-p2.z));
    return CrossProductSquare(vec1, vec2);
}

//同色点组成的三角形获取最大面积
double GetMaxAreaSquare(vector<Point> points){
    double maxAreaSquare=-1;
    for(int i=0; i<points.size(); i++){
        for(int j=i+1; j<points.size(); j++){
            for(int k=j+1; k<points.size(); k++){
                maxAreaSquare=max(maxAreaSquare,GetAreaSquare(points[i], points[j], points[k]));
            }
        }
    }
    return maxAreaSquare;
}

//三色点组成三角形获取最大面积
double GetMaxAreaSquare(vector<Point> redPoints, vector<Point> greenPoints, vector<Point> bluePoints){
    double maxAreaSquare=-1;
    for(int i=0; i<redPoints.size(); i++){
        for(int j=0; j<greenPoints.size(); j++){
            for(int k=0; k<bluePoints.size(); k++){
                maxAreaSquare=max(maxAreaSquare,GetAreaSquare(redPoints[i], greenPoints[j], bluePoints[k]));
            }
        }
    }
    return maxAreaSquare;
}

int main()
{
    vector<Point> redPoints, greenPoints, bluePoints;
    int N;
    char color;
    int x, y, z;
    cin>>N;
    for(int i=0; i<N; i++){
        cin>>color>>x>>y>>z;
        Point point=Point(x, y, z);
        if(color=='R'){
            redPoints.push_back(point);
        }
        else if(color=='G'){
            greenPoints.push_back(point);
        }
        else if(color=='B'){
            bluePoints.push_back(point);
        }
    }
    double maxArea=0;
    maxArea=max(maxArea, GetMaxAreaSquare(redPoints));
    maxArea=max(maxArea, GetMaxAreaSquare(greenPoints));
    maxArea=max(maxArea, GetMaxAreaSquare(bluePoints));
    maxArea=max(maxArea, GetMaxAreaSquare(redPoints, greenPoints, bluePoints));
    printf("%.5lf", sqrt(maxArea)/2.0);
    return 0;
}