92 return (p1.x - p2.x) * (p1.x - p2.x) + (p1.
y - p2.
y) * (p1.
y - p2.
y);
104 int val = (q.y - p.
y) * (r.x - q.x) - (q.x - p.x) * (r.
y - q.y);
109 return (val > 0) ? 1 : 2;
119int compare(
const void *vp1,
const void *vp2) {
120 auto *p1 =
static_cast<const Point *
>(vp1);
121 auto *p2 =
static_cast<const Point *
>(vp2);
124 int o = orientation(p0, *p1, *p2);
126 return (distSq(p0, *p2) >= distSq(p0, *p1)) ? -1 : 1;
129 return (o == 2) ? -1 : 1;
140 int ymin = points[0].y,
min = 0;
141 for (
int i = 1; i < size; i++) {
145 if ((y < ymin) || (ymin == y && points[i].x < points[min].x)) {
146 ymin = points[i].y,
min = i;
164 for (
int i = 1; i < size; i++) {
166 while (i < size - 1 && orientation(p0, points[i], points[i + 1]) == 0) {
170 points[m] = points[i];
187 for (
int i = 3; i < m; i++) {
191 while (St.
size() > 1 &&
192 orientation(nextToTop(&St), St.
top(), points[i]) != 2) {
200 while (!St.
empty()) {