Longest envelope of the set of points
I want to find the longest envelope of the set of points, means that the longest line that circumvent each point in the set I have input, and then calculate its length. My idea is to find the edge point in every line, there are 3 case:
1. no points - go to the next line,
2. 1 point - put it into array twice,
3, 2 or more points, then find the most on the left and the most on the right.
I intend to start putting them into array at the ery top of, this time input coordinates, then proceed left, so if there is only one point in a line and "m" is a number of non-empty lines, its coordinates would be Arr[i].x,Arr[i].y and
Arr[i+m].x,Arr[i+m].y
My input was
3
1 2
3 4
5 6
The program crashed. I tried working with debugger but it was of no help, since I do not fulluy understand the way the debugger works.
I put my code.
thanks for help in advance.
Code:
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <ctime>
#include <math.h>
typedef struct {
int x;
int y;
} point;
int ScanningNumberOfPoints();
void GeneratingPoints(int n, point tab[200]);
void FindingExtremePositions(point tab[200], int n, point Arr[1000], int m); // two points in each line; one most on right, and one most on left
void Distance (point Arr1[1000], int n, int m);
int main()
{
int m=0; // size of an array of extreme points
point tab[200]; // array of all coordinates
point Arr[1000]; //array of extreme points
int n = ScanningNumberOfPoints(); // number of randomly generated points
GeneratingPoints(n, tab);
FindingExtremePositions(tab, n, Arr, m);
Distance (Arr, n, m);
}
int ScanningNumberOfPoints()
{
int n;
printf("input how many points you'd like to see:\n");
scanf("%d", &n);
return n;
}
void GeneratingPoints(int n, point tab[200])
{
for(int i =0; i < n; i++)
{
scanf("%d", &tab[i].x);
scanf("%d", &tab[i].y);
}
}
void FindingExtremePositions( point tab[200], int n, point Arr[1000], int m)
{
int max=0;
int min=1000;
int licznik = 0;
int licznik1 = 0;
//half of the points
int a; //The highest point
int d=0;
int numerpodwojnejlinii;
int zapamietajmaxwpodwojnejlinii=0;
int zapamietajminwpodwojnejlinii =111;
for(int i=0;i<50;i++)
{
for(int y=0;y<50;y++)
{
if(tab[y].x!=i) //HOW MANY POINTS ARE IN ONE LINE
{
m++; // NUMBER OF EMPTY LINES
}
}
}
for(int i=0;i<n;i++)
{
if(tab[i].y>max)
{
max=tab[i].y;
a=i;
}
}
for(int i=0;i<50;i++)
{
for(int a=0;a<50;a++)
{
if(tab[a].y==i) //HOW MANY POINTS ARE IN ONE LINE
{
d++;
numerpodwojnejlinii=i;
}
}
if(d==0)
{}
else
if(d==1)
{
Arr[i].x=tab[i].x;
Arr[i].y=tab[i].y;
Arr[i+m].x=tab[i].x;
Arr[i+m].y=tab[i].y;
}
if(d>=2)
{
for(int r=0;r<n;r++)
{
if(tab[r].y==numerpodwojnejlinii)
{
if(tab[r].x>max)
{
max=tab[r].x;
zapamietajmaxwpodwojnejlinii=r;
}
if(tab[r].x<min)
{
min=tab[r].x;
zapamietajminwpodwojnejlinii=r;
}
}
}
Arr[i].x=tab[zapamietajmaxwpodwojnejlinii].x;
Arr[i].y=tab[zapamietajmaxwpodwojnejlinii].y;
Arr[i+m].x=tab[zapamietajminwpodwojnejlinii].x;
Arr[i+m].y=tab[zapamietajminwpodwojnejlinii].y;
//numerpodwojnejlinii=0;
//zapamietajmaxwpodwojnejlinii=0;
//zapamietajminwpodwojnejlinii=110;
//max=0;
// min=100;
}
}
}
void Distance (point Arr[1000], int n, int m)
{
double sum=0;
for(int i = 0;i<2*m;i++)
{
sum+=sqrt(pow((Arr[i+1].x-Arr[i].x),2)+pow((Arr[i+1].y-Arr[i].y),2));
}
sum=sum+sqrt(pow((Arr[2*m-1].x-Arr[0].x),2)+pow((Arr[2*m-1].y-Arr[0].y),2));
printf("%lf\n", sum);
}
