int findModule const point p1 const point p2 int ax ay ax p2 p1 ay p2

 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
int findModule(const point &p1, const point &p2){
int ax, ay;
ax = p2.x - p1.x;
ay = p2.y - p1.y;
return sqrt(ax*ax + ay*ay);
}
int findAngle (const point &p1, const point &p2, const point &p3){
int ax, ay, bx, by;
ax = p2.x - p1.x;
ay = p2.y - p1.y;
bx = p3.x - p1.x;
by = p3.y - p1.y;
return ax*by - ay*bx;
}
void findConvexHull(vector <point> &p, vector <point> &c){
point temp = p[0]; int it = -1;
for(int i = 1; i < p.size(); i++){
if (p[i].y <= temp.y)
if(p[i].y < temp.y) { temp = p[i]; it = i; }
else if(p[i].x < temp.x) { temp = p[i]; it = i; };
}
c.push_back(temp);
if (it != -1) p.erase(p.begin() + it);
else p.erase(p.begin());
do{
it = -1;
temp = c.front();
for(int i = 0; i < p.size(); i++){
int angle = findAngle(c.back(), temp, p[i]);
if(angle <= 0)
if (angle < 0) { temp = p[i]; it = i; }
else if ( ( findModule(c.back(), p[i]) - findModule(c.back(), temp) > 0 ) ) { temp = p[i]; it = i; }
}
c.push_back(temp);
if (it != -1) p.erase(p.begin() + it);
else p.clear();
} while (temp.x != c.front().x || temp.y != c.front().y);
}