44 #ifdef CHECK_MEMORY_LEAKS
46 #endif // CHECK_MEMORY_LEAKS
58 int n = (
int) V.size();
59 std::vector<Position> D(2 * n + 1);
60 int bot = n - 2, top = bot + 3;
61 D[bot] = D[top] = V[2];
62 if (
isLeft(V[0], V[1], V[2]) > 0) {
71 for (
int i = 3; i < n; i++) {
73 if (bot >= (
int) D.size() || top - 1 >= (
int) D.size() || i >= (
int) V.size()) {
76 if ((
isLeft(D[bot], D[bot + 1], V[i]) > 0) &&
77 (
isLeft(D[top - 1], D[top], V[i]) > 0)) {
83 while (
isLeft(D[bot], D[bot + 1], V[i]) <= 0) {
85 if (bot >= (
int) D.size()) {
94 if (top == 0 || top >= (
int) D.size()) {
98 while (
isLeft(D[top - 1], D[top], V[i]) <= 0) {
100 if (top == 0 || top >= (
int) D.size()) {
105 if (top + 1 >= (
int) D.size()) {
114 for (h = 0; h <= (top - bot); h++) {
115 if (bot + h >= (
int) D.size()) {