include iostream include cmath include locale include conio include ve

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <iostream>
#include <cmath>
#include <locale.h>
#include <conio.h>
#include <vector>
#include <time.h>
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 <int> parts;
int first = 0,j = 0,past = 0;
int d = 0;
vector<int>::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<<x[d]<<"\t"<<y[d];
cout<<endl;
}
cout << endl << "Количество точек выпуклой оболочки: " << parts.size() << endl << endl;
}
int main(){
int n = 0, i = 0;
setlocale(LC_ALL,"Rus");
cout << "Алгоритм Джарвиса:" << endl;
cout << "Количество точек на плоскости: ";
cin >> 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;
}