Цель работы. Построить выпуклый многоугольник по алгоритму Джарвиса, методу обхода Грэхема Постановка задачи. Пусть на плоскости дано множество точек. Нужно построить выпуклый многоугольник, чтобы для любой точки из заданного множества было верно одно из трех утверждений: а) точка является вершиной построенного многоугольника; б) точка принадлежит одной из сторон многоугольника; в) точка лежит внутри многоугольника.
Вот #include <bits/stdc++.h> using namespace std; struct Point { int x, y; bool operator < (const Point &p) const { return x < p.x || (x == p.x && y < p.y); } }; int cross(Point A, Point B) { return A.x * B.y - A.y * B.x; } vector<Point> jarvis(vector<Point> P) { int n = P.size(); vector<Point> H(2 * n); sort(P.begin(), P.end()); int k = 0; for (int i = 0; i < n; i++) { while (k >= 2 && cross(H[k - 2] - H[k - 1], P[i] - H[k - 1]) < 0) k--; H[k++] = P[i]; } for (int i = n - 2, t = k + 1; i >= 0; i--) { while (k >= t && cross(H[k - 2] - H[k - 1], P[i] - H[k - 1]) < 0) k--; H[k++] = P[i]; } H.resize(k - 1); return H; } int main() { int n; cin >> n; vector<Point> P(n); for (int i = 0; i < n; i++) cin >> P[i].x >> P[i].y; vector<Point> H = jarvis(P); for (int i = 0; i < H.size(); i++) cout << H[i].x << " " << H[i].y << endl; return 0; } Код #include <bits/stdc++.h> using namespace std; struct Point { int x, y; bool operator < (const Point &p) const { return x < p.x || (x == p.x && y < p.y); } }; int cross(Point A, Point B) { return A.x * B.y - A.y * B.x; } vector<Point> jarvis(vector<Point> P) { int n = P.size(); vector<Point> H(2 * n); sort(P.begin(), P.end()); int k = 0; for (int i = 0; i < n; i++) { while (k >= 2 && cross(H[k - 2] - H[k - 1], P[i] - H[k - 1]) < 0) k--; H[k++] = P[i]; } for (int i = n - 2, t = k + 1; i >= 0; i--) { while (k >= t && cross(H[k - 2] - H[k - 1], P[i] - H[k - 1]) < 0) k--; H[k++] = P[i]; } H.resize(k - 1); return H; } int main() { int n; cin >> n; vector<Point> P(n); for (int i = 0; i < n; i++) cin >> P[i].x >> P[i].y; vector<Point> H = jarvis(P); for (int i = 0; i < H.size(); i++) cout << H[i].x << " " << H[i].y << endl; return 0; }