Witam. Chce znalezc najdluzsza obwiednie losowo wygenerowanych punktow, tj aby wszystkie punkty byly w mozliwie najdluzyszm obrysie, ktorego wierzcholkami bede punkty.
zabralem sie do tego nastepujaco: wygenerowlem punkty - dziala.
Nastepnie wybieram skrajne pkt w kazdej linijce, i chce policzyc dystans miedzy nimi -> nie dziala.
Zamieszczam kod, proszac madrzejszych ode mnie o przewertowanie. Z gor dziekuje.
#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 PrintingPoints(int n, point tab[200]);
void FindingExtremePositions(point tab[200], int n, point Arr[1000], int size); // two points in each line; one most on right, and one most on left
void Distance (point Arr1[1000], int n, int size);
int main()
{
int size; // size of an array of extreme points
point tab[200]; // array of all coordinates
point Arr[1000]; //array of extreme points
point Arr1[1000]; // array of en envelope of the set of points
int n = ScanningNumberOfPoints(); // number of randomly generated points
GeneratingPoints(n, tab);
PrintingPoints(n, tab);
FindingExtremePositions(tab, n, Arr, size);
Distance (Arr1, n, size);
}
void GeneratingPoints(int n, point tab[200])
{
srand((unsigned)time(NULL));
int b,c;
b=40; // upper bond of generated coordinates
c=0; // lower bond of generated coordinates
for(int i =0; i < n; i++)
{
tab[i].x = (b-c)*rand()/double(RAND_MAX) + c;
tab[i].y = (b-c)*rand()/double(RAND_MAX) + c;
}
}
void PrintingPoints(int n, point tab[200]) // Printing points to given coordinates
{
for(int k = 0 ; k < 40; k++)
{
for(int a = 0; a < 40; a++)
{
bool prt = true;
for(int i = 0 ; i < n; i++)
{
if(k==(40 - tab[i].y) && (a == tab[i].x) )
prt = false;
}
if(prt)
{
printf(" ");
}
else
printf("*");
}
printf("\n");
}
}
int ScanningNumberOfPoints()
{
int n;
printf("input how many points you'd like to see:\n");
scanf("%d", &n);
return n;
}
void FindingExtremePositions( point tab[200], int n, point Arr[1000], int size)
{
int max=0;
int min=1000;
int licznik = 0;
int licznik1 = 0;
for(int i=0;i<n;i++) // in this loop i find points most on right
{
if(tab[i].x>20) // twenty is the middle of the board I print points on
{
licznik++;
for(int a=0;a<n;a++)
{
if(tab[i].x==tab[a].x)
{
if(tab[a].y>max)
{
max=tab[a].y;
Arr[i].x=tab[i].x;
Arr[i].y=tab[a].y;
}
}
}
}
}
for(int i=0;i<n;i++) // in this loop i find points most on left
{
if(tab[i].x<20)
{
licznik1++;
for(int a=0;a<n;a++)
{
if(tab[i].x==tab[a].x)
{
if(tab[a].y<min)
{
min=tab[a].y;
Arr[licznik+i].x=tab[i].x; //to prevent overlappinvg the index of an array I conrinue using an array from the last occupied index
Arr[licznik+i].y=tab[a].y;
}
}
}
}
}
size = licznik +licznik1;
}
void Distance (point Arr[1000], int n, int size)
{
double sum=0;
for(int i = 0;i<size-1;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[size-1].x-Arr[0].x),2)+pow((Arr[size-1].y-Arr[0].y),2));
printf("%lf\n", sum);
}