Longest envelope of the set of points

This is a discussion on Longest envelope of the set of points within the C Programming forums, part of the General Programming Boards category; I want to find the longest envelope of the set of points, means that the longest line that circumvent each ...

  1. #1
    Registered User
    Join Date
    Jan 2013
    Posts
    1

    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);
    }

  2. #2
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    Check again if some counter goes out of bounds.
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  3. #3
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,822
    Longest thread so far is found here -> Longest envelope of the set of points. - Dev Shed

    Take time to read this -> How To Ask Questions The Smart Way
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 3
    Last Post: 03-26-2012, 06:12 PM
  2. C++ Plot Simple Points / Graph, X & Y array points
    By Khadafi in forum C++ Programming
    Replies: 9
    Last Post: 11-11-2011, 03:47 AM
  3. Help with getting longest string
    By bosredsox247 in forum C++ Programming
    Replies: 20
    Last Post: 09-22-2006, 06:50 PM
  4. Decimal Points and Binary Points
    By Shadow12345 in forum A Brief History of Cprogramming.com
    Replies: 9
    Last Post: 11-07-2002, 01:06 AM
  5. Why does the little envelope thing beside my topic always have a black seal on it?
    By skyruler54 in forum A Brief History of Cprogramming.com
    Replies: 1
    Last Post: 09-01-2002, 05:51 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21