0

```
#include <iostream>
#include <vector>
using namespace std;
class Pair {
public:
Pair(int a, int b)
{x=a; y=b;};
int get_x()
{return x;};
int get_y()
{return y;};
private:
int x;
int y;};
int main()
{vector<Pair> set;
\\input of the set of points, with 50 points
Pair* a1 = new Pair(70, 64); set.push_back(*a1);
Pair* a2 = new Pair(3, 11); set.push_back(*a2);
Pair* a3 = new Pair(43, 35); set.push_back(*a3);
Pair* a4 = new Pair(67, 97); set.push_back(*a4);
Pair* a5 = new Pair(95, 71); set.push_back(*a5);
Pair* a6 = new Pair(53, 70); set.push_back(*a6);
Pair* a7 = new Pair(79, 13); set.push_back(*a7);
Pair* a8 = new Pair(53, 66); set.push_back(*a8);
Pair* a9 = new Pair(47, 81); set.push_back(*a9);
Pair* a10 = new Pair(69, 42); set.push_back(*a10);
Pair* a11 = new Pair(66, 96); set.push_back(*a11);
Pair* a12 = new Pair(87, 2); set.push_back(*a12);
Pair* a13 = new Pair(57, 9); set.push_back(*a13);
Pair* a14 = new Pair(74, 41); set.push_back(*a14);
Pair* a15 = new Pair(19, 33); set.push_back(*a15);
Pair* a16 = new Pair(44, 53); set.push_back(*a16);
Pair* a17 = new Pair(32, 85); set.push_back(*a17);
Pair* a18 = new Pair(41, 75); set.push_back(*a18);
Pair* a19 = new Pair(63, 89); set.push_back(*a19);
Pair* a20 = new Pair(47, 20); set.push_back(*a20);
Pair* a21 = new Pair(68, 98); set.push_back(*a21);
Pair* a22 = new Pair(58, 53); set.push_back(*a22);
Pair* a23 = new Pair(95, 12); set.push_back(*a23);
Pair* a24 = new Pair(51, 80); set.push_back(*a24);
Pair* a25 = new Pair(19, 33); set.push_back(*a25);
Pair* a26 = new Pair(25, 3); set.push_back(*a26);
Pair* a27 = new Pair(78, 5); set.push_back(*a27);
Pair* a28 = new Pair(29, 48); set.push_back(*a28);
Pair* a29 = new Pair(1, 54); set.push_back(*a29);
Pair* a30 = new Pair(45, 6); set.push_back(*a30);
Pair* a31 = new Pair(30, 59); set.push_back(*a31);
Pair* a32 = new Pair(20, 92); set.push_back(*a32);
Pair* a33 = new Pair(80, 80); set.push_back(*a33);
Pair* a34 = new Pair(17, 67); set.push_back(*a34);
Pair* a35 = new Pair(79, 24); set.push_back(*a35);
Pair* a36 = new Pair(10, 84); set.push_back(*a36);
Pair* a37 = new Pair(45, 3); set.push_back(*a37);
Pair* a38 = new Pair(6, 10); set.push_back(*a38);
Pair* a39 = new Pair(12, 16); set.push_back(*a39);
Pair* a40 = new Pair(60, 17); set.push_back(*a40);
Pair* a41 = new Pair(85, 53); set.push_back(*a41);
Pair* a42 = new Pair(70, 36); set.push_back(*a42);
Pair* a43 = new Pair(53, 98); set.push_back(*a43);
Pair* a44 = new Pair(94, 4); set.push_back(*a44);
Pair* a45 = new Pair(46, 48); set.push_back(*a45);
Pair* a46 = new Pair(56, 85); set.push_back(*a46);
Pair* a47 = new Pair(63, 35); set.push_back(*a47);
Pair* a48 = new Pair(41, 56); set.push_back(*a48);
Pair* a49 = new Pair(39, 74); set.push_back(*a49);
Pair* a50 = new Pair(50, 14); set.push_back(*a50);
vector<Pair> hull;
\\checking for every combination of two points wheter they are a part of the convex hull
for (int p=0; p<set.size(); p++){
for (int q=0; q<set.size(); q++){
\\forming coordinates of the pair of points
int px=set[p].get_x(); int py=set[p].get_y();
int qx=set[q].get_x(); int qy=set[q].get_y();
\\proceed only if the two points are different
if (!((px==qx) && (py==qy))) {int cnt=0;
\\performing a check for every single point in the set whether it is below
\\the line formed by the 2 points (this means that the two points are a part of the hull)
for (int i=0; i<set.size(); i++){
int p2x=set[i].get_x(); int p2y=set[i].get_y();
\\performing a coordinate translation so that the first point is at 0,0
px=px-qx; py=py-qy; p2x=p2x-qx; p2y=p2y-qy; qx=0; qy=0;
\\finding the determinant
double det = ((px-qx)*(p2y-qy)) - ((p2x-qx)*(py-qy));
\\if the determinant is lower then zero, that means that the point is above the line formed by the 2 points
if (det<0) cnt++;}
\\in case all of the points are above the line, the counter cnt will be 50
if (cnt==50) {int tcntx=0, tcnty=0;
\\checking if the points are already added to the hull
for (int i=0; i<hull.size(); i++){
int ix=set[i].get_x(); int iy=set[i].get_y();
if ((px==ix) && (py==iy)) tcntx++;
if ((qx==ix) && (qy==iy)) tcnty++;}
\\if not we add them
if (tcntx==0) hull.push_back(set[p]);
if (tcnty==0) hull.push_back(set[q]);}
}}}
\\printing the result
for (int p=0; p<hull.size(); p++){cout<<"("<<hull[p].get_x()<<", "<<hull[p].get_y()<<")"<<endl;}
cout<<endl<<hull.size()<<endl;
\\check for validity of algorithm, connecting 2 points and counting how many points are below and how many above the line
int x1=1,x2=3,y1=54,y2=10, up=0,down=0;
for (int i=0; i<set.size(); i++){
int p2x=set[i].get_x(); int p2y=set[i].get_y();
x1=x1-x2; y1=y1-y2; p2x=p2x-x2; p2y=p2y-y2; x2=0; y2=0;
double det = ((x1-x2)*(p2y-y2)) - ((p2x-x2)*(y1-y2));
if (det>=0) down++; else up ++;}
cout<<endl<<up<<endl<<down<<endl<<up+down<<endl;
system("PAUSE");
return 0;
}
```

Please take a look at the code, it should find the convex hull of 50 given points. I tried to use a simple approach which algorithm is something like this:

CODE:

1. for all points p in S

2. for all points q in S

3. if p != q

4. draw a line from p to q

5. if all points in S except p and q lie to the left of the line add the directed vector pq to the solution set

I just try to collect the convex hull points and if possible to sort them in order. I have a logical problem in the program, the syntax should be correct and the code is compilable.

Please help if you can, every hint is of great importance.