Выпуклый многоугольник

выпуклую оболочку можно найти с помощью алгоритма Грэхема. В вашем случае если после построения выпуклой оболочки останутся лишние точки то из ваших точек нельзя построить выпуклую оболочку.

Алгоритм. Найдём самую левую и самую правую точки A и B (если таких точек несколько, то возьмём самую нижнюю среди левых, и самую верхнюю среди правых). Понятно, что и A, и B обязательно попадут в выпуклую оболочку. Далее, проведём через них прямую AB, разделив множество всех точек на верхнее и нижнее подмножества S1 и S2 (точки, лежащие на прямой, можно отнести к любому множеству - они всё равно не войдут в оболочку). Точки A и B отнесём к обоим множествам. Теперь построим для S1 верхнюю оболочку, а для S2 - нижнюю оболочку, и объединим их, получив ответ. Чтобы получить, скажем, верхнюю оболочку, нужно отсортировать все точки по абсциссе, затем пройтись по всем точкам, рассматривая на каждом шаге кроме самой точки две предыдущие точки, вошедшие в оболочку. Если текущая тройка точек образует не правый поворот (что легко проверить с помощью Ориентированной площади), то ближайшего соседа нужно удалить из оболочки. В конце концов, останутся только точки, входящие в выпуклую оболочку.

Итак, алгоритм заключается в сортировке всех точек по абсциссе и двух (в худшем случае) обходах всех точек, т.е. требуемая асимптотика O (N log N) достигнута.

#include <vector>
#include <algorithm>

struct Point
{
  double x, y;
};

bool cmp(Point a, Point b)
{
  return a.x < b.x || a.x == b.x && a.y < b.y;
}

bool cw(Point a, Point b, Point c)
{
  return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y) < 0;
}

bool ccw(Point a, Point b, Point c) {
  return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y) > 0;
}

void convex_hull(std::vector<Point>& a)
{
  if (a.size() == 1) {
    return;
  }

  std::sort(a.begin(), a.end(), &cmp);
  Point p1 = a[0], p2 = a.back();
  std::vector<Point> up, down;
  up.push_back(p1);
  down.push_back(p1);

  for (size_t i = 1; i < a.size(); ++i) {
    if (i == a.size() - 1 || cw(p1, a[i], p2)) {
      while (up.size() >= 2 && !cw(up[up.size() - 2], up[up.size() - 1], a[i])) {
        up.pop_back();
      }
      up.push_back(a[i]);
    }
    if (i == a.size() - 1 || ccw(p1, a[i], p2)) {
      while (down.size() >= 2 && !ccw(down[down.size() - 2], down[down.size() - 1], a[i])) {
        down.pop_back();
      }
      down.push_back(a[i]);
    }
  }

  a.clear();
  for (size_t i = 0; i < up.size(); ++i) {
    a.push_back(up[i]);
  }
  for (size_t i = down.size() - 2; i > 0; --i) {
    a.push_back(down[i]);
  }
}

материал взят с сайта e-maxx.ru

Не нужно строить выпуклую оболочку чтобы проверить что простой многоугольник является выпуклым. Вы упустили один-единственный случай: три точки могут оказаться на одной прямой. В этом случае вы не можете полагаться на

bool isccw = ccw(p[n - 1], p[0], p[1]);

Исправить можно просто: отыщите самую нижнюю вершину, если их несколько, то из них выберите самую левую. isccw нужно считать на этой тройке.

И в цикле тоже надо учитывать что три или более точек могут лежать на одной прямой. Функцию ccw надо будет переделать так чтобы она могла возвращать три состояния.

Альтернативное решение - посчитать ccw на всех тройках вершин и убедится что она не возвращает и "лево" и "право". Так, наверно, проще:

// g++ -std=c++11 -pedantic -Wall -Wextra is_convex.cpp

#include <bits/stdc++.h>

struct Point {
    int x;
    int y;
};

int read_int() {
    int i;
    std::cin >> i;
    return i;
}

Point read_point() {
    int x = read_int();
    int y = read_int();
    return {x, y};
}

Point operator -(const Point& a, const Point& b) {
    return {a.x - b.x, a.y - b.y};
}

int cross(const Point& a, const Point& b) {
    return a.x * b.y - a.y * b.x;
}

int area2(const Point& a, const Point& b, const Point& c) {
    return cross(c - a, c - b);
}

class Clock {
public:
    Clock(const Point& p1, const Point& p2) : p1(p1), p2(p2), has_ccw(false), has_cw(false) {}
    bool update(const Point& p3) {
        int a = area2(p1, p2, p3);
        has_ccw = has_ccw || a < 0;
        has_cw = has_cw || a > 0;
        p1 = p2;
        p2 = p3;
        return has_ccw && has_cw;
    }
private:
    Point p1;
    Point p2;
    bool has_ccw;
    bool has_cw;
};

bool is_convex() {
    const int n = read_int();
    const Point first = read_point();
    const Point second = read_point();

    Clock c(first, second);

    for (int i = 2; i < n; ++i) {
        if (c.update(read_point())) {
            return false;
        }
    }
    if (c.update(first)) {
        return false;
    }
    if (c.update(second)) {
        return false;
    }
    return true;
}

int main() {
    std::ios_base::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0);
    std::cout << (is_convex() ? "YES" : "NO");
    return 0;
}