I am trying to solve this problem (just convex hull with Graham’s scan). My code doesn’t even pass the sample test case. I get three points instead of four. I can’t find the error in my implementation. Can someone please help me fix it?
Code
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
#define eb emplace_back
#define F first
#define S second
#define mp make_pair
template <typename Container>
void print(Container& container)
{
auto Start = container.begin(), End = container.end();
while (Start != End) cout << *(Start++) << " ";
cout << '\n';
}
typedef double ftype;
struct point {
ftype x, y;
point() {};
point(int x, int y) : x(x), y(y) {}
point& operator += (const point& t) {
x += t.x;
y += t.y;
return *this;
}
point& operator -= (const point& t) {
x -= t.x;
y -= t.y;
return *this;
}
point& operator *= (ftype t) {
x *= t;
y *= t;
return *this;
}
point& operator /= (ftype t) {
x /= t;
y /= t;
return *this;
}
point operator + (const point& t) const {
return point(*this) += t;
}
point operator - (const point& t) const {
return point(*this) -= t;
}
point operator * (ftype t) const {
return point(*this) *= t;
}
point operator / (ftype t) const {
return point(*this) /= t;
}
};
ftype cross(point a, point b) {
return a.x * b.y - a.y * b.x;
}
ftype signed_area_parallelogram(point a, point b, point c) {
return cross(b - a, c - b);
}
bool clockwise(point a, point b, point c) {
return signed_area_parallelogram(a, b, c) < 0;
}
bool counter_clockwise(point a, point b, point c) {
return signed_area_parallelogram(a, b, c) > 0;
}
bool cmp(point& a, point& b) {
return a.x < b.x || (a.x == b.x && a.y < b.y);
}
void convex_hull(vector <point>& a) {
if (a.size() == 1) return;
sort(a.begin(), a.end(), cmp);
point p1 = a.front(), p2 = a.back();
vector <point> up, down;
up.push_back(p1);
down.push_back(p1);
for (int i = 1; i < (int)a.size(); ++i) {
if (i == (int)a.size() - 1 || clockwise(p1, a[i], p2)) {
while ((int)up.size() >= 2 && !clockwise(up[(int)up.size() - 2], up[(int)up.size() - 1], a[i])) up.pop_back();
up.push_back(a[i]);
}
if (i == (int)a.size() - 1 || counter_clockwise(p1, a[i], p2)) {
while ((int)down.size() >= 2 && !counter_clockwise(down[(int)down.size() - 2], down[(int)down.size() - 1], a[i])) down.pop_back();
down.push_back(a[i]);
}
}
a.clear();
for (int i = 0; i < (int)up.size(); ++i) a.push_back(up[i]);
for (int i = (int)down.size() - 2; i > 0; --i) a.push_back(up[i]);
}
inline void solve()
{
int n;
cin >> n;
vector <point> points(n);
for (auto& [x, y] : points) cin >> x >> y;
convex_hull(points);
cout << points.size() << '\n';
for (const auto& [x, y] : points) cout << x << " " << y << '\n';
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
while (t--) solve();
}
If you prefer a link: click