Thread: Simple c++ convex hull help

  1. #1
    Registered User
    Join Date
    Jan 2012
    Posts
    5

    Simple c++ convex hull help

    Hi all !!
    I am currently writing a simple c++ program that computes the convex hull of random given points.
    As I don't know mch about programming yet I am trying to use the simple Brute force method.


    What I am trying to do s read a number from in.txt which will show how many pairs of coordinates follow and I will have to find which of the pairs are on the corners of the convex hull.
    In out.txt I have first a number showing how many the answers that follow are and then the rest of the numbers have to be the line in which the pair of coordinates were given in in.txt in ascending order
    e.g.
    in.txt out.txt
    10 6
    1 5 1
    2 10 2
    5 5 7
    3 8 8
    6 10 9
    8 7 10
    9 10
    8 11
    9 3
    3 1
    Code:
    #include <iostream>
    #include <stdio.h>
    using namespace std;
    int main ()
    {
         int n,i,j,k,l,count,count0,co;
        int apot [n];
         int sinx [n];
         int siny [n];
        bool flag=true;
         FILE *read = fopen("in.txt", "r");
         FILE *write = fopen("out.txt", "w");
         fscanf (read,"%ld",& n); // read the amount of points that are given
         count=0;
         count0=0;
         co=0;
         
            for (i=0 ; i<n ; i++)
            {
               fscanf (read,"%ld",& sinx [i]);
               fscanf (read,"%ld",& siny [i]); // read the coordinates
     
            }
            for (i=0;i<n;i++)
            {
                for (j=0;j<n;j++)
                {
                    for (k=0;k<n;k++)
                    {
     
                        if ((sinx[j]-sinx[i])*(siny[k]-siny[i])-(siny[j]-siny[i])*(sinx[k]-sinx[i])> 0)    //if all that is >0 it will be on one side of the line
                        {
                            count++;              
                        }
                        else if ((sinx[j]-sinx[i])*(siny[k]-siny[i])-(siny[j]-siny[i])*(sinx[k]-sinx[i])<0) // if it is <0 then it will be on the other side of the line
                        {
                            count--;              
                        }
                        else if ((sinx[j]-sinx[i])*(siny[k]-siny[i])-(siny[j]-siny[i])*(sinx[k]-sinx[i])==0)
                        {
                            count0++;       // if it is ==0 then I put it into another counter and add/substract it at the end      
                        }
     
                        } 
                        if (count<0)                     
                        {                            
                            count=count-count0; // if the rest is all on one side i substract those that are on it
                        }                           
                        else if (count>=0) // or in this case I add it to the oter conter
                        {
                        count=count+count0;
                        }
                            if (count== n || count==(-1*n)) // if the counter is ==n then all points will be on one side of it
                        {
                            for (l=0;l<=i;l++)   // here I check the answers array to make sure there aren't any duplicates  
                            {
                            if (i==apot[l])        
                            {
                                flag=false;
                            }
     
                        }
                        if (flag==true) // if there aren't any duplicates then add i+1 to the counter
                        {co++;
                             apot[co] = (i+1);     // i+1 because i starts from 0 to go to n-1 
                             
                        }
     
                        }
                        count=0;   
                        count0=0;
                }
                flag=true;   
            }
        fprintf (write,"%d",co); // this will be the number of answers
        for (i=0;i<n;i++)
            {
               
                    fprintf (write,"\n");
                    fprintf (write,"%ld",apot [i]); // the answers one under the other
                    
                    }
     
            
     
            return 0;
            }

  2. #2
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    This is C, not C++. What makes you think otherwise?
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  3. #3
    Registered User
    Join Date
    Oct 2006
    Posts
    250
    Quote Originally Posted by Elysia View Post
    This is C, not C++. What makes you think otherwise?
    And yet another extremely helpful comment by Elysia! Your post count has now been increased! (Incidentally, so has mine)
    iMalc: Your compiler doesn't accept misspellings and bad syntax, so why should we?
    justin777: I have no idea what you are talking about sorry, I use a laptop and there is no ascii eject or something

  4. #4
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    And yet another extremely helpful comment by MWAAAHAAA! Your post count has now been increased! (Incidentally, so has mine)
    And we yet another example of a user posting in the wrong section, causing anguish to some members who do not wish to involve themselves with C and tend to avoid any threads on the C section.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  5. #5
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > fscanf (read,"%ld",& n); // read the amount of points that are given
    Except your arrays have already been "sized" with the garbage uninitialised value in n, long before you get to this line.

    > #include <iostream>
    > #include <stdio.h>
    But Elysia is right - decide which language you want to program in and stick to it.

    Just throwing any old rubbish together and just accepting "well it compiles" isn't the way to go.
    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.

  6. #6
    Registered User
    Join Date
    Jan 2012
    Posts
    5
    Quote Originally Posted by Salem View Post
    > fscanf (read,"%ld",& n); // read the amount of points that are given
    Except your arrays have already been "sized" with the garbage uninitialised value in n, long before you get to this line.

    > #include <iostream>
    > #include <stdio.h>
    But Elysia is right - decide which language you want to program in and stick to it.

    Just throwing any old rubbish together and just accepting "well it compiles" isn't the way to go.

    So I have to read the number first and then declare the arrays
    like this : (?)
    Code:
    int main ()
    {
         int n,i,j,k,l,count,count0,co;
        bool flag;
         FILE *read = fopen("in.txt", "r");
         FILE *write = fopen("out.txt", "w");
         fscanf (read,"%ld",& n); // read the amount of points that are given
         int apot [n];
         int sinx [n];
         int siny [n];
         count=0;
         count0=0;
         co=0;
         flag=true;

  7. #7
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Something like that, except variable length arrays are only standard in C99.

    Plus "%ld" should just be plain "%d" for reading into an integer.

    So do we assume that this is now a C program?
    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.

  8. #8
    Registered User
    Join Date
    Jan 2012
    Posts
    5
    Quote Originally Posted by Salem View Post
    So do we assume that this is now a C program?
    Don't ask me. I only started programming a few months ago

    But the program as it is doesn't work. Any more sugestions ?

  9. #9
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    Quote Originally Posted by Stamatis View Post
    Don't ask me. I only started programming a few months ago
    And yet the decision is yours. Why don't you flip a coin?
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  10. #10
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Quote Originally Posted by Stamatis View Post
    But the program as it is doesn't work. Any more sugestions ?
    To help you, we need to know what language you intend to learn.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  11. #11
    Registered User
    Join Date
    Jan 2012
    Posts
    5
    Quote Originally Posted by Elysia View Post
    To help you, we need to know what language you intend to learn.
    C++ probably.

  12. #12
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    In that case, you need to read up on how to do I/O proper with C++. There are tutorials on the site, if it helps.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. convex hull using c
    By sunils120 in forum C Programming
    Replies: 1
    Last Post: 08-29-2011, 06:50 AM
  2. Convex Hulls
    By arundhatibakshi in forum Tech Board
    Replies: 6
    Last Post: 10-06-2005, 12:27 AM
  3. Convex Hull <#>
    By Moni in forum C++ Programming
    Replies: 6
    Last Post: 06-07-2003, 09:45 AM
  4. Replies: 1
    Last Post: 07-20-2002, 06:33 PM