This documentation is automatically generated by competitive-verifier/competitive-verifier
// @brief Static Convex Hull
#define PROBLEM "https://judge.yosupo.jp/problem/static_convex_hull"
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("tune=native")
#include "cp-algo/geometry/convex_hull.hpp"
#include <bits/stdc++.h>
using namespace std;
using namespace cp_algo::geometry;
using point = point_t<int64_t>;
void solve() {
int n;
cin >> n;
vector<point> r(n);
for(auto &it: r) {
it.read();
}
auto res = convex_hull(r);
cout << size(res) << "\n";
for(auto it: res) {
it.print();
}
}
signed main() {
//freopen("input.txt", "r", stdin);
ios::sync_with_stdio(0);
cin.tie(0);
int t = 1;
cin >> t;
while(t--) {
solve();
}
}
#line 1 "verify/geometry/hull.test.cpp"
// @brief Static Convex Hull
#define PROBLEM "https://judge.yosupo.jp/problem/static_convex_hull"
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("tune=native")
#line 1 "cp-algo/geometry/convex_hull.hpp"
#line 1 "cp-algo/geometry/point.hpp"
#line 1 "cp-algo/random/rng.hpp"
#include <chrono>
#include <random>
namespace cp_algo::random {
uint64_t rng() {
static std::mt19937_64 rng(
std::chrono::steady_clock::now().time_since_epoch().count()
);
return rng();
}
}
#line 4 "cp-algo/geometry/point.hpp"
#include <iostream>
#include <complex>
namespace cp_algo::geometry {
template<typename ftype>
struct point_t: public std::complex<ftype> {
using Base = std::complex<ftype>;
using Base::Base;
point_t(Base const& t): Base(t) {}
auto operator <=> (point_t const& t) const {
return std::pair{y(), -x()} <=> std::pair{t.y(), -t.x()};
}
ftype x() const {return Base::real();}
ftype y() const {return Base::imag();}
point_t cmul(point_t const& t) const {return conj(*this) * t;}
ftype dot(point_t const& t) const {return cmul(t).x();}
ftype cross(point_t const& t) const {return cmul(t).y();}
static constexpr point_t O = {0, 0};
int half() const {
return *this < O ? -1 : *this == O ? 0 : 1;
}
static bool ccw(point_t const& a, point_t const& b) {
return a.cross(b) > 0;
}
static bool ccw_abs(point_t const& a, point_t const & b) {
return std::tuple{a.half(), (ftype)0, norm(a)} <
std::tuple{b.half(), a.cross(b), norm(b)};
}
void read() {
ftype _x, _y;
std::cin >> _x >> _y;
*this = {_x, _y};
}
void print() const {
std::cout << x() << ' ' << y() << "\n";
}
};
}
#line 4 "cp-algo/geometry/convex_hull.hpp"
#include <algorithm>
#include <utility>
#include <vector>
#include <ranges>
namespace cp_algo::geometry {
template<typename ftype>
std::vector<point_t<ftype>> convex_hull(std::vector<point_t<ftype>> r) {
using point = point_t<ftype>;
std::ranges::sort(r);
if(size(r) <= 1 || r[0] == r.back()) {
return empty(r) ? r : std::vector{r[0]};
}
std::vector<point> hull = {r[0]};
for(int half: {0, 1}) {
size_t base = size(hull);
for(auto it: std::views::drop(r, 1)) {
while(size(hull) >= base + 1) {
point a = hull.back();
if(point::ccw(it - a, end(hull)[-2] - a)) {
break;
} else {
hull.pop_back();
}
}
hull.push_back(it);
}
std::ranges::reverse(r);
std::ignore = half;
}
hull.pop_back();
return hull;
}
}
#line 6 "verify/geometry/hull.test.cpp"
#include <bits/stdc++.h>
using namespace std;
using namespace cp_algo::geometry;
using point = point_t<int64_t>;
void solve() {
int n;
cin >> n;
vector<point> r(n);
for(auto &it: r) {
it.read();
}
auto res = convex_hull(r);
cout << size(res) << "\n";
for(auto it: res) {
it.print();
}
}
signed main() {
//freopen("input.txt", "r", stdin);
ios::sync_with_stdio(0);
cin.tie(0);
int t = 1;
cin >> t;
while(t--) {
solve();
}
}
Env | Name | Status | Elapsed | Memory |
---|---|---|---|---|
g++ | all_same_00 | AC | 62 ms | 4 MB |
g++ | all_same_01 | AC | 62 ms | 4 MB |
g++ | example_00 | AC | 5 ms | 4 MB |
g++ | example_01 | AC | 5 ms | 3 MB |
g++ | max_ans_00 | AC | 149 ms | 29 MB |
g++ | max_colinear_00 | AC | 106 ms | 19 MB |
g++ | max_colinear_01 | AC | 103 ms | 19 MB |
g++ | max_random_00 | AC | 114 ms | 19 MB |
g++ | max_random_01 | AC | 78 ms | 19 MB |
g++ | max_random_02 | AC | 99 ms | 19 MB |
g++ | max_random_03 | AC | 106 ms | 19 MB |
g++ | max_random_04 | AC | 115 ms | 19 MB |
g++ | max_random_05 | AC | 80 ms | 19 MB |
g++ | max_random_06 | AC | 100 ms | 19 MB |
g++ | max_random_07 | AC | 107 ms | 19 MB |
g++ | near_circle_00 | AC | 135 ms | 25 MB |
g++ | near_circle_01 | AC | 135 ms | 25 MB |
g++ | small_random_00 | AC | 118 ms | 4 MB |
g++ | small_random_01 | AC | 95 ms | 3 MB |
g++ | small_random_02 | AC | 94 ms | 4 MB |
g++ | small_random_03 | AC | 96 ms | 4 MB |
g++ | small_random_04 | AC | 120 ms | 3 MB |
g++ | small_random_05 | AC | 94 ms | 3 MB |
g++ | small_random_06 | AC | 96 ms | 3 MB |
g++ | small_random_07 | AC | 96 ms | 3 MB |