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