# How to write points in this algorithm

• 06-17-2011
animation
How to write points in this algorithm
Hi all!

I have found Andrew's monotone convex hull algorithm implemented on the net:
Algorithm Implementation/Geometry/Convex hull/Monotone chain - Wikibooks, open books for an open world

This is perfect for me, but I have an irritating problem... I just can't figure out how to use the stuct Point. Here's the implementation:
Code:

```// Implementation of Andrew's monotone chain 2D convex hull algorithm. // Asymptotic complexity: O(n log n). // Practical performance: 0.5-1.0 seconds for n=1000000 on a 1GHz machine. #include <algorithm> #include <vector> using namespace std;   typedef int coord_t;        // coordinate type typedef long long coord2_t;  // must be big enough to hold 2*max(|coordinate|)^2   struct Point {         coord_t x, y;           bool operator <(const Point &p) const {                 return x < p.x || (x == p.x && y < p.y);         } };   // 2D cross product of OA and OB vectors, i.e. z-component of their 3D cross product. // Returns a positive value, if OAB makes a counter-clockwise turn, // negative for clockwise turn, and zero if the points are collinear. coord2_t cross(const Point &O, const Point &A, const Point &B) {         return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x); }   // Returns a list of points on the convex hull in counter-clockwise order. // Note: the last point in the returned list is the same as the first one. vector<Point> convex_hull(vector<Point> P) {         int n = P.size(), k = 0;         vector<Point> H(2*n);           // Sort points lexicographically         sort(P.begin(), P.end());           // Build lower hull         for (int i = 0; i < n; i++) {                 while (k >= 2 && cross(H[k-2], H[k-1], P[i]) <= 0) k--;                 H[k++] = P[i];         }           // Build upper hull         for (int i = n-2, t = k+1; i >= 0; i--) {                 while (k >= t && cross(H[k-2], H[k-1], P[i]) <= 0) k--;                 H[k++] = P[i];         }           H.resize(k);         return H; }```
If i for example want to use the method cross(), then what do I write? This seems the most logical: cross(1.1, 3.9, 11.0), but this is read as doubles.

I don't want to use the cross method of cause, just to understand how Points are written, so I can supply the convex_hull method with a vector containing these Points.

Best regards
Jannick
• 06-17-2011
m37h0d
the function accepts Points, a pair of x and y values, not single numbers. you need to declare instances of Points, assign values to their members, and pass them into the function.
• 06-18-2011
animation
Quote:

Originally Posted by m37h0d
the function accepts Points, a pair of x and y values, not single numbers. you need to declare instances of Points, assign values to their members, and pass them into the function.

Cool!
Code:

`Point a = {2,5};`