-
May 18th, 2011, 01:59 PM
#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;
}
-
May 18th, 2011, 02:39 PM
#2
Re: Covex Hull Issues
Victor Nijegorodov
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|