CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 2 of 2
  1. #1
    Join Date
    May 2011
    Posts
    1

    Covex Hull Issues

    Hello guys !!!

    I am struggling with one C++ assignment and all help will be appreciated !!!
    Here is the assignment and the Code that I have managed to put together. I am exhausted and depleted... please assist further !
    I do not have any idea regarding point 4.
    ---------------------------------- Assignment ---------------------------------------

    Given set of points in the plane, you have to write a program in C++ that computes the following values:

    1. The minimal distance between two points.
    2. The maximal distance between two points.
    3. The largest area of a triangle which has vertices at given points.
    4. The area of a convex hull of the set of points.

    73 58
    45 19
    89 6
    22 40
    92 16
    65 66
    55 4
    45 18
    64 13
    56 81
    73 33
    58 40
    40 71
    90 60
    16 47
    6 52
    62 91
    90 83
    69 78
    61 62
    71 57
    32 53
    67 91
    83 89
    14 53
    45 35
    11 6
    9 50
    70 65
    50 47
    65 57
    40 68
    44 40
    77 61
    27 59
    27 54
    94 89
    90 88
    61 66
    72 4
    11 41
    3 74
    44 33
    47 79
    68 33
    32 64
    66 23
    55 12
    37 54
    28 95


    ---------------------------------- Code so far ---------------------------------------

    #include <iostream>
    #include <math>
    using namespace std;

    #define N_PNT 50

    typedef struct TPoint {
    int x;
    int y;
    } TPT;

    TPT Points[] =
    {{73, 58}, {45, 19}, {89, 6}, {22, 40}, {92, 16}, {65, 66},
    {55, 4}, {45, 18}, {64, 13}, {56, 81}, {73, 33}, {58, 40},
    {40, 71}, {90, 60}, {16, 47}, {6, 52}, {62, 91}, {90, 83},
    {69, 78}, {61, 62}, {71, 57}, {32, 53}, {67, 91}, {83, 89},
    {14, 53}, {45, 35}, {11, 6}, {9, 50}, {70, 65}, {50, 47},
    {65, 57}, {40, 68}, {44, 40}, {77, 61}, {27, 59}, {27, 54},
    {94, 89}, {90, 88}, {61, 66}, {72, 4}, {11, 41}, {3, 74},
    {44, 33}, {47, 79}, {68, 33}, {32, 64}, {66, 23}, {55, 12},
    {37, 54}, {28, 95}};

    double GetDistancePoints( TPT A, TPT B )
    {
    return( sqrt( pow( (B.x - A.x), 2 ) + pow( (B.y - A.y), 2 ) ) );
    }

    int main(int argc, char* argv[])
    {
    int i, j, k,
    MaxI, MaxJ, MinI, MinJ, MaxSI, MaxSJ, MaxSK;
    double MaxD, MinD, D, A, B, C, P, S, MaxS;

    for ( i = 0; i < N_PNT; i++ )
    for ( j = i + 1; j < N_PNT; j++ ) {
    D = GetDistancePoints( Points[i], Points[j] );
    if ( i == 0 && j == 1 ) {
    MaxD = MinD = D;
    MaxI = MinI = 0;
    MaxJ = MinJ = 1;
    }
    else {
    if ( D > MaxD ) {
    MaxD = D;
    MaxI = i;
    MaxJ = j;
    }

    if ( D < MinD ) {
    MinD = D;
    MinI = i;
    MinJ = j;
    }
    }
    }

    for ( i = 0; i < N_PNT; i++ )
    for ( j = i + 1; j < N_PNT; j++ )
    for ( k = j + 1; k < N_PNT; k++ ) {
    A = GetDistancePoints( Points[i], Points[j] );
    B = GetDistancePoints( Points[i], Points[k] );
    C = GetDistancePoints( Points[j], Points[k] );
    P = (A + B + C) / 2;
    S = sqrt( P * (P - A) * (P - B) * (P - C) );

    if ( i == 0 && j == 1 && k == 2 ) {
    MaxS = S;
    MaxSI = i;
    MaxSJ = j;
    MaxSK = k;
    }
    else
    if ( MaxS < S ) {
    MaxSI = i;
    MaxSJ = j;
    MaxSK = k;
    MaxS = S;
    }
    }

    cout << "1) MinDistancePoints = " << MinD << " between points P"
    << MinI + 1 << "(" << Points[MinI].x << ", "
    << Points[MinI].y << ") and "
    << "P" << MinJ + 1 << "(" << Points[MinJ].x << ", "
    << Points[MinJ].y << ");" << endl;

    cout << "2) MaxDistancePoints = " << MaxD << " between points P"
    << MaxI + 1 << "(" << Points[MaxI].x << ", "
    << Points[MaxI].y << ") and "
    << "P" << MaxJ + 1 << "(" << Points[MaxJ].x << ", "
    << Points[MaxJ].y << ");" << endl;

    cout << "3) Largest area of triangle = " << MaxS << " with points P"
    << MaxSI + 1 << "(" << Points[MaxSI].x << ", "
    << Points[MaxSI].y << ") and "
    << "P" << MaxSJ + 1 << "(" << Points[MaxSJ].x << ", "
    << Points[MaxSJ].y << ") and "
    << "P" << MaxSK + 1 << "(" << Points[MaxSK].x << ", "
    << Points[MaxSK].y << ");" << endl;

    system( "pause" );

    return 0;
    }

  2. #2
    VictorN's Avatar
    VictorN is offline Super Moderator Power Poster
    Join Date
    Jan 2003
    Location
    Hanover Germany
    Posts
    20,396

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured