Warning: session_start(): open(/var/lib/php/sessions/sess_olbkcmp2l6rl3u1ps2d305qq0q, O_RDWR) failed: No space left on device (28) in /var/www/tb-usercake/models/config.php on line 51

Warning: session_start(): Failed to read session data: files (path: /var/lib/php/sessions) in /var/www/tb-usercake/models/config.php on line 51
// from https://www.geeksforgeeks.org/convex-hull-using-jarvis-algorithm-or-wrapping/ sclass ConvexHull2D { settable IDoublePt[] points; gettable new L hull; // To find orientation of ordered triplet (p, q, r). // The function returns following values // 0 --> p, q and r are collinear // 1 --> Clockwise // 2 --> Counterclockwise int orientation(IDoublePt p, IDoublePt q, IDoublePt r) { double val = (q.y_double() - p.y_double()) * (r.x_double() - q.x_double()) - (q.x_double() - p.x_double()) * (r.y_double() - q.y_double()); if (val == 0) ret 0; // collinear ret val > 0 ? 1 : 2; // clock or counterclock wise } run { int n = l(points); // Less than 3 points -> hull is all points if (n < 3) ret with hull = points; hull.clear(); // Find the leftmost point int l = 0; for (int i = 1; i < n; i++) if (points[i].x_double() < points[l].x_double()) l = i; // Start from leftmost point, keep moving // counterclockwise until we reach the start point // again. This loop runs O(h) times where h is the // number of points in the hull. int p = l, q; do { // Add current point to result hull.add(points[p]); // Search for a point 'q' such that // orientation(p, q, x) is counterclockwise // for all points 'x'. The idea is to keep // track of last visited most counterclock- // wise point in q. If any point 'i' is more // counterclock-wise than q, then update q. q = (p + 1) % n; for i to n: { // If i is more counterclockwise than // current q, then update q if (orientation(points[p], points[i], points[q]) == 2) q = i; } // Now q is the most counterclockwise with // respect to p. Set p as q for next iteration, // so that q is added to result 'hull' p = q; } while (p != l); // While we don't come to first point } }