Using Exhaustive Search, this program will find all possible triangles but provide the smallest area to the end-user.

BruteForceTriangles.cpp

// =====================================================
// Programmer:      Nicholas Gautier
// Class:           CS3713; Algorithm Analysis
// Assignment #:    2
// Due Date:        8. March. 2018
// Instructor:      Mr. Moinian, Feridoon
// Description:     This program will perform an exhaustive search to find
//                  all possible triangles and report back the results of
//                  all triangles.  However, it will also provide information
//                  regarding the smallest triangle area.
//                  -----
//                  WARNING: If running this program under *NIX, please comment
//                      LINE190.  This instruction is only for running this
//                      program under the Windows platform.
//
// NOTE: I am using Visual Studio 2017.
// ----
// COMPILING NOTES FOR G++
//  - NOTHING YET - 
// ----
// Return Codes:
//  0 = Successful Operation
//  !0 = See Operating System Documentation
// =====================================================


#pragma region Inclusions
#include <iostream>     // For input and output
#include <cmath>        // For sqrt() and pow()
#include <string>       // We will need this for displaying a string datatype
#pragma endregion


// ----


// Class Definition
// This will hold the X and Y values of a plot point within
//  the Cartesian plain.
class PlotData
{
public:
    int x;      // Holds the 'x' value of the point
    int y;      // Holds the 'y' value of the point
}; // CLASS :: PlotData



// Class Definition
// This will contain all of the information associated with the triangle.
class TriangleData
{
public:
    int x0;         // Holds the 'x' value of the first point
    int y0;         // Holds the 'y' value of the first point
    int x1;         // Holds the 'x' value of the second point
    int y1;         // Holds the 'y' value of the second point
    double area;    // This will hold the area of the triangle.
    bool valid;     // This bool flag will state if the triangle is valid.
                    //  If the triangle lines are already in use, than it is not valid.
                    //  In addition, if the triangle is NOT really a triangle - than it is not valid.
                    //  In short: True = Valid Triangle and can be used.
                    //            False = Not valid and is ignored.
}; // CLASS :: TriangleData


// ----


#pragma region Function Prototypes
void DrawHeader();                  // Draw the program's header information into the terminal buffer
void DrawAbout();                   // Draw the About section within the terminal buffer
void DrawInstructions();            // Draw the Instructions section within the terminal buffer.
void GeneratePoints(PlotData[],
                    int);           // Issue hard-coded values
double CalculateArea(int,
                    int,
                    int,
                    int);           // This function will perform the triangle area calculation.
void DisplayOneTriData(
                       TriangleData[],
                       int);        // This function will display one triangle data within the array index key.
int FindSmallestTriArea(
                        TriangleData[],
                        int);       // This function will find a triangle with the smallest area possible.
#pragma endregion


// ----


#pragma region Macros
#define _NAME_ "Triangles'O Plenty!"            // Program Name
#define _VERSION_ "1.0"                         // Program Version
#define _VERSION_NAME_ "CornMazes"              // Version Name
#define _ARRAY_PLOTPOINT_SAMPLE_SIZE_ 10        // The sample size provided by the Requirements
                                                // Maximum Array size that will
                                                //  hold the plot points within
                                                //  2D Cartesian plain.
#define _ARRAY_COMBINATION_CHANCES_SIZE_ 120    // Using the combination formula: (10!)/(3!(10-3)!)
#pragma endregion



// Main Program Entry
// ----------------------------
// The main entry point of the program
int main()
{
    // Initialization and Declarations
    // ================================
    PlotData pointArr[_ARRAY_PLOTPOINT_SAMPLE_SIZE_];       // This will hold our plot points within the Cartesian plain.
    TriangleData triArr[_ARRAY_COMBINATION_CHANCES_SIZE_];  // This will hold our triangle data
    int indexHighlighter = 0;                               // We will use this for indexing the Triangle Data array.
    int smallestTriangleAreaIndex;                          // We will use this for storing the index of the smallest triangle data.
    // --------------------------------

    // Program Information and Details
    // ================================
    // Display the program header
    DrawHeader();
    // Provide some spacing on the terminal buffer
    std::cout << std::endl;
    // Display the program's about message
    DrawAbout();
    // Provide some spacing on the terminal buffer
    std::cout << std::endl;
    // Display the instructions
    DrawInstructions();
    // Provide some spacing on the terminal buffer
    std::cout << std::endl;
    // --------------------------------

    // Main Program Instructions
    // ################################

    // Generate the plot points
    std::cout << "Auto-Generating Plot Points within the 2D Cartesian Plain. . ."   << std::endl;
    GeneratePoints(pointArr, _ARRAY_PLOTPOINT_SAMPLE_SIZE_);     // Grossly setup the plot points.

    // Gather the triangle data
    //  * Cache the plot points determined to be the triangle
    //  * Calculate the area
    std::cout << "Gathering Triangle Data. . ." << std::endl << std::endl;

    for (int i = 0; i < _ARRAY_PLOTPOINT_SAMPLE_SIZE_ - 1; i++)
        for (int j = i + 1; j < _ARRAY_PLOTPOINT_SAMPLE_SIZE_; j++)     // Thank you Mr. Moinian!
        {
            triArr[indexHighlighter].x0 = pointArr[i].x;                    // Cache the 'x' value from the first line
            triArr[indexHighlighter].y0 = pointArr[i].y;                    // Cache the 'y' value from the first line
            triArr[indexHighlighter].x1 = pointArr[j].x;                    // Cache the 'x' value from the second line
            triArr[indexHighlighter].y1 = pointArr[j].y;                    // Cache the 'y' value from the second line
            triArr[indexHighlighter].area = CalculateArea(pointArr[i].x,
                                                            pointArr[i].y,
                                                            pointArr[j].x,
                                                            pointArr[j].y); // Find the triangle area

            // Determine if Calculate Area returned an error
            if (triArr[indexHighlighter].area == -9999.99)
                triArr[indexHighlighter].valid = false;     // The Triangle data provided is not a real triangle.
            else
                triArr[indexHighlighter].valid = true;      // The Triangle data provided is a valid triangle.

            // Display the information
            DisplayOneTriData(triArr, indexHighlighter);

            // Provide some spacing on the terminal buffer
            std::cout << std::endl << std::endl;

            // Update the Triangle Data Array index pointer
            indexHighlighter++;
        } // Inner-Loop

    // ----

    // Find the smallest triangle area possible
    std::cout << "Finding the smallest triangle area. . ." << std::endl;
    smallestTriangleAreaIndex = FindSmallestTriArea(triArr, indexHighlighter);

    // ----

    // Found the smallest area, display the results.
    std::cout << "The smallest area possible is: " << std::endl;
    DisplayOneTriData(triArr, smallestTriangleAreaIndex);
    
    // ----
    
    // <<!>> WINDOWS EXTCMD INSTRUCTION <<!>>
    // COMMENT THIS LINE IF RUNNING ON THE *NIX PLATFORMS!
    system("PAUSE");    // Do NOT destroy the console instance immediately after the results has been
                        //  displayed on the screen for a few nano-seconds, instead issue a pause
                        //  instruction so that the user can see the results.

    // Prepare the termination process
    std::cout << std::endl << "Terminating program. . ." << std::endl;
    return 0;
} // main()


// ----


// Draw Header
// ------------------------------------
// This function will provide a header to the top-most space on
//  the terminal buffer.
void DrawHeader()
{
    std::cout << _NAME_ << " - Version: " << _VERSION_ << std::endl
        << "Version Name: " << _VERSION_NAME_ << std::endl
        << "--------------------------------------------" << std::endl;
} // DrawHeader()


// ----


// Draw Instructions
// ------------------------------------
// This function will provide instructions to the end-user, along
//  with how this program works.
void DrawInstructions()
{
    std::cout << "Instructions" << std::endl
        << "-----------------------------" << std::endl
        << "This program will automatically generate values for you, no interaction is necessary." << std::endl
        << "=========================================" << std::endl;
} // DrawInstructions()


// ----


// Draw About
// ------------------------------------
// This function is merely designed to display what this program is about and its primary purpose.
void DrawAbout()
{
    std::cout << "This program will perform an exhaustive search of each possible triangle and calculate their areas using the Triangle Area formula."
        << "When all possible triangles have been calculated, we will then find then try to find the smallest possible area."
        << "With that information, this program will present that result to the user."
        << std::endl
        << std::endl
        << "NOTE: All plot points within the 2D Cartesian Plain is hardcoded into the program.  Thus, no input is necessary from the user."
        << std::endl;
} // DrawAbout()


// ----


// Generate Plot Points
// ------------------------------------
// This function will provide the hard coded values of the plot-points within the Cartesian plain.
// The values have been provided by the Requirements.
// ------------------------------------
// Parameters
//  arr[] (PlotData)
//      This is a container for holding all of our plot points.
//  size (INTEGER)
//      The maximum size of plot points.
void GeneratePoints(PlotData arr[], int size)
{
    // Provide the points into the array container
    // NOTE: I could have just thrown the values instantly into array
    //      during the initialization, but where's the fun in that?
    //      Lets over complicate this!
    //      Also, I just wanted an excuse to use a Switch() within a
    //      for-loop.  YAY!
    for (int i = 0; i < size; i++)
        switch (i)
        {
        case 0 :
            arr[i].x = -6;
            arr[i].y = 0;
            break;
        case 1 :
            arr[i].x = -2;
            arr[i].y = 2;
            break;
        case 2 :
            arr[i].x = 0;
            arr[i].y = 8;
            break;
        case 3 :
            arr[i].x = 1;
            arr[i].y = 1;
            break;
        case 4 :
            arr[i].x = 5;
            arr[i].y = 4;
            break;
        case 5 :
            arr[i].x = 7;
            arr[i].y = 2;
            break;
        case 6 :
            arr[i].x = 2;
            arr[i].y = -1;
            break;
        case 7 :
            arr[i].x = 1;
            arr[i].y = -4;
            break;
        case 8 :
            arr[i].x = -2;
            arr[i].y = -3;
            break;
        case 9 :
            arr[i].x = -6;      // The original value was: -5, but changed in 1 March.
            arr[i].y = -4;      // The original value was: -4, but changed in 1 March.
            break;
        } // Switch
} // GeneratePoints()


// ----


// Calculate Triangle Area
// ------------------------------------
// This function will calculate the area of the triangle.
// NOTE: We automatically assume that we will ALWAYS use the origin.
// ------------------------------------
// Parameters
//  x0 [INTEGER]
//      This holds the 'x' value of the first plot point
//  y0 [INTEGER]
//      This holds the 'y' value of the first plot point
//  x1 [INTEGER]
//      This holds the 'x' value of the second plot point
//  y1 [INTEGER]
//      This holds the 'y' value of the second plot point
// ------------------------------------
// Output
//  Triangle Area [FLOAT]
//      This is the triangle area that was calculated.
//      If we find that the information provided is NOT a triangle,
//      than an output of '-9999.99' will be presented.
//      Thus, '-9999.99' is an error; the data provided does not contain a triangle.
double CalculateArea(int x0, int y0, int x1, int y1)
{
    // Initializations and Declarations
    // ================================
    double a;       // Line distance; [(0, 0) -> (x0, y0)]
    double b;       // Line distance; [(x0, y0) -> (x1, y1)]
    double c;       // Line distance; [(x1, y1) -> (0, 0)]
    double s;       // Semi-perimeter of the triangle
    double area;    // Area of the triangle
    // --------------------------------

    // Get the line distance
    a = double(sqrt(pow((0 - x0),2) + pow((0 - y0), 2)));       // Line Distance: (0, 0) -> (x0, y0)
    b = double(sqrt(pow((x0 - x1), 2) + pow((y0 - y1), 2)));    // Line Distance: (x0, y0) -> (x1, y1)
    c = double(sqrt(pow((x1 - 0), 2) + pow((y1 - 0), 2)));      // Line Distance: (x1, y1) -> (0, 0)

    // Check if the lines hold true for a plausible triangle
    //  If not, return an error of '-9999.99'.
    if (a + b < c || a + c < b || b + c < a)
        return -9999.99;    // Not a valid triangle

    // Find the Semi-Perimeter
    s = double((a + b + c) / 2);

    // Find the area of the triangle
    area = double(sqrt(s * (s - a) * (s - b) * (s - c)));

    // Return the area of the triangle
    return double(area);
} // CalculateArea()


// ----


// Display Individual Triangle Data
// ------------------------------------
// This function will merely display the triangle data (from the array) using an index
//  pointer to select the individual triangle data.  This function will only display
//  ONE result from the array.
// ------------------------------------
// Parameters
//  arr[] [TriangleData]
//      The Triangle Data that we will access to get the information from.
//  indexKey
//      The index pointer to select an item from the Triangle Data array.
void DisplayOneTriData(TriangleData arr[], int indexKey)
{
    // Initializations and Declarations
    // ---------------------------------
    std::string validResult;        // We will use this to convert a '0' or a '1'
                                    //  into something more understandable to the end-user.
    // ---------------------------------

    // Convert a 0 or 1 to something more meaningful to the user.
    if (arr[indexKey].valid)
        validResult = "Yes";
    else
        validResult = "No";

    // Present the information
    std::cout << "Triangle Data ID: " << indexKey << std::endl
        << "Plot Points: " << "(0, 0) (" << arr[indexKey].x0 << ", " << arr[indexKey].y0 << ") (" << arr[indexKey].x1 << ", " << arr[indexKey].y1 << ")" << std::endl
        << "Area Calculated: " << arr[indexKey].area << std::endl
        << "Triangle Valid: " << validResult
        << std::endl;
} // DisplayOneTriData()


// ----


// Find the Smallest Triangle Area
// ------------------------------------
// This function will locate the smallest possible triangle and
//  return the index to the calling function.
//  Any triangles within the array that contain 'Non-Valid'
//  triangle information will be ignored.
// ------------------------------------
// Parameters
//  arr[] [TriangleData]
//      The Triangle Data array we will access from.
//  size
//      The size of the triangle array we will access.
int FindSmallestTriArea(TriangleData arr[], int size)
{
    // Initialization and Declarations
    // --------------------------------
    double smallestArea;    // We will use this to cache the smallest triangle area.
    int indexKey;           // This will hold the index within the Triangle Data
                            // array that has the smallest triangle area.
    // --------------------------------

    // Cache the first index
    smallestArea = arr[0].area;
    indexKey = 0;

    // Make sure we have more than one element within the Triangle Data array.
    if (size > 0)
        // Scan the array
        for (int i = 1; i < size; i++)
        {
            // Is the triangle at this index valid?
            if (arr[i].valid == false)
                continue;   // If the triangle is not valid, than proceed to the next index.

            // Is the area smaller than what was previously cached?
            else if (arr[i].area < smallestArea)
            {
                smallestArea = arr[i].area;     // Update the smallest area
                indexKey = i;                   // Update the index to match with the
                                                //  triangle with the smallest area.
            } // IF :: Update Smallest Area
        } // FOR :: Scan Array

    // Return the index that contains the smallest area.
    return indexKey;
} // FindSmallestTriArea()