#include #include #include #include #include #include using namespace std; double angle(int *x, int *y, int j, int i, int way){ return 0.5 * (x[way] * y[j] + x[j] * y[i] + x[i] * y[way] - y[way] * x[j] - y[j] * x[i] - y[i] * x[way]); } int point(int *x, int *y, int way,int j,int i) { double a = sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])); double b = sqrt((x[i]-x[way])*(x[i]-x[way])+(y[i]-y[way])*(y[i]-y[way])); if (b < a) return 1; else return 0; } void JARVIS(int *x, int *y, int n){ vector parts; int first = 0,j = 0,past = 0; int d = 0; vector::iterator it; double mean; first = 0; for(int i = 1; i < n-1; i++){ if (x[i] < x[first] || (x[i] == x[first] && y[i] < y[first])) first = i; } j = first; do{ parts.push_back(j); past = j; for (int i = n - 1; i >= 0; -- i) if (x[i] != x[j] || y[i] != y[j]){ mean = angle(x, y, j, i, past); if (past == j || mean > 0 || (mean == 0 && point(x, y, past, j, i))) past = i; } j = past; } while(j!=first); cout << endl << "Точки выпуклой оболочки:" << endl; for (it = parts.begin(); it!=parts.end(); ++it){ d=*it; cout<> n; int *x = new int [n]; int *y = new int [n]; srand(time(NULL)); for(i = 0; i < n; i++){ x[i]=rand()%200+10; y[i]=rand()%300+10; } for(i = 0; i < n; i++) { cout << x[i] << "\t"; cout << y[i] << endl; } JARVIS(x, y, n); delete x; delete y; }