competitive-programming-library
This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub kmyk/competitive-programming-library
Andrew's Monotone Chain
(old/a.inc.cpp)
- View this file on GitHub
- Last update: 2020-01-08 18:35:19+09:00
Code
typedef complex<double> point;
double cross(point a, point b) { return a.real() * b.imag() - a.imag() * b.real(); }
int ccw(point a, point b, point c) { double z = cross(b - a, c - a); return z > eps ? 1 : z < - eps ? -1 : 0; }
/**
* @brief Andrew's Monotone Chain
*/
vector<point> convex_hull(vector<point> ps) {
int n = ps.size();
sort(ALL(ps), [&](point a, point b) { return make_pair(a.real(), a.imag()) < make_pair(b.real(), b.imag()); });
vector<point> ch(2 * n);
int k = 0;
for (int i = 0; i < n; ch[k ++] = ps[i ++]) // lower-hull
while (k >= 2 and ccw(ch[k - 2], ch[k - 1], ps[i]) <= 0) -- k;
for (int i = n - 2, t = k + 1; i >= 0; ch[k ++] = ps[i --]) // upper-hull
while (k >= t and ccw(ch[k - 2], ch[k - 1], ps[i]) <= 0) -- k;
ch.resize(k - 1);
return ch;
}
struct circle { point p; double r; };
struct line { point s, t; };
struct segment { point s, t; };
struct ray { point s, t; };
/**
* @note あまり小さくすると誤差で死ぬ
*/
const double eps = 1e-6;
double sq(double x) { return pow(x, 2); }
struct point { double y, x; };
point operator + (point a, point b) { return (point) { a.y + b.y, a.x + b.x }; }
point operator - (point a, point b) { return (point) { a.y - b.y, a.x - b.x }; }
point operator * (point a, double b) { return (point) { a.y * b, a.x * b }; }
point operator / (point a, double b) { return (point) { a.y / b, a.x / b }; }
point operator < (point a, point b) { return make_pair(a.y, a.x) < make_pair(b.y, b.x); }
double distance(point a, point b) { return sqrt(sq(a.y - b.y) + sq(a.x - b.x)); }
double dot(point a, point b) { return a.x * b.x + a.y * b.y; }
double cross(point a, point b) { return a.x * b.y - a.y * b.x; }
int ccw(point a, point b, point c) { double z = cross(b - a, c - a); return z > eps ? 1 : z < - eps ? -1 : 0; }
/**
* @brief segment - segment, inclusive
*/
bool does_intersect(segment const & a, segment const & b){
return ccw(a.s, a.t, b.s) * ccw(a.s, a.t, b.t) <= 0 and
ccw(b.s, b.t, a.s) * ccw(b.s, b.t, a.t) <= 0;
}
/**
* @brief point and line
*/
bool does_intersect(point a, line b) { return ccw(0, a - b.s, b.t - b.s) == 0; }
bool does_intersect(line a, point b) { return does_intersect(b, a); }
/**
* @brief line and line
*/
bool is_parallel(line a, line b) { return ccw(0, a.t - a.s, b.t - b.s) == 0; }
bool is_same(line a, line b) { return does_intersect(a.s, b) and does_intersect(a.t, b); }
/**
* @note false if two lines are the same
*/
bool does_intersect(line a, line b) {
return not is_parallel(a, b)
and not is_same(a, b);
}
point intersection(line a, line b) {
assert (does_intersect(a, b));
double p = cross(a.t - a.s, b.t - b.s);
double q = cross(a.t - a.s, a.t - b.s);
return (q / p) * (b.t - b.s) + b.s;
}
/**
* @note helper for segments and rays
*/
template <typename T, typename U>
bool does_intersect_linelikes(T const & a, U const & b) {
if (not does_intersect(to_line(a), to_line(b))) return false;
point c = intersection(to_line(a), to_line(b));
return does_intersect(c, a)
and does_intersect(c, b);
}
line to_line(segment a) {
return { a.s, a.t };
}
bool does_intersect(point a, segment b) {
return abs(cross(b.t - b.s, a - b.s)) < eps
and dot(b.t - b.s, a - b.s) > - eps
and dot(b.s - b.t, a - b.t) > - eps;
}
bool does_intersect(segment a, point b) {
return does_intersect(b, a);
}
bool is_overwraped(segment a, segment b) {
return does_intersect(a.s, b)
and does_intersect(a.t, b);
}
bool does_intersect(segment a, segment b) {
return does_intersect_linelikes(a, b);
}
point intersection(segment a, segment b) {
assert (does_intersect(a, b));
return intersection(to_line(a), to_line(b));
}
line to_line(ray a) {
return { a.s, a.t };
}
bool does_intersect(point a, ray b) {
return abs(cross(b.t - b.s, a - b.s)) < eps
and dot(b.t - b.s, a - b.s) > - eps;
}
bool does_intersect(ray a, point b) {
return does_intersect(b, a);
}
bool is_overwraped(ray a, ray b) {
return (does_intersect(a.s, b) and does_intersect(a.t, b))
or (does_intersect(b.s, a) and does_intersect(b.t, a));
}
bool does_intersect(ray a, ray b) {
return does_intersect_linelikes(a, b);
}
point intersection(ray a, ray b) {
assert (does_intersect(a, b));
return intersection(to_line(a), to_line(b));
}
struct polygon { vector<point> ps; };
segment nth_segment(polygon const & a, int i) {
int j = (i+1) % a.ps.size();
return { a.ps[i], a.ps[j] };
}
bool does_intersect(ray a, segment b) { return does_intersect_linelikes(a, b); }
bool does_intersect(segment a, ray b) { return does_intersect_linelikes(a, b); }
point intersection(ray a, segment b) { return intersection_linelikes(a, b); }
point intersection(segment a, ray b) { return intersection_linelikes(a, b); }
template <typename T>
vector<point> intersections_polygon_linelike(polygon const & a, T const & b) {
vector<point> result;
repeat (i, a.ps.size()) {
if (does_intersect(nth_segment(a, i), b)) {
result.push_back(intersection(nth_segment(a, i), b));
}
}
return result;
}
bool does_intersect(polygon const & a, ray const & b) {
return not intersections_polygon_linelike(a, b).empty();
}
bool does_intersect(polygon const & a, point const & b) {
ray c = { b, b + point(1, 0) };
return intersections_polygon_linelike(a, c).size() % 2 == 1;
}
bool does_intersect_strict(polygon const & a, point const & b) {
repeat (i, a.ps.size()) {
if (does_intersect(nth_segment(a, i), b)) {
return false; // when the point is on a segment of the polygon
}
}
return does_intersect(a, b);
}
bool does_intersect_strict(polygon const & a, segment const & b) { // the boundary is not included
vector<point> ps = intersections_polygon_linelike(a, b);
for (point p : ps) {
bool ignored = false;
if (abs(p - b.s) < eps or abs(p - b.t) < eps) {
ignored = true;
}
if (not ignored) {
for (point q : a.ps) {
if (abs(p - q) < eps) {
ignored = true; // when the intersection point is one of the vertex of the polygon
break;
}
}
}
if (not ignored) return true;
}
return false;
}#line 1 "old/a.inc.cpp"
typedef complex<double> point;
double cross(point a, point b) { return a.real() * b.imag() - a.imag() * b.real(); }
int ccw(point a, point b, point c) { double z = cross(b - a, c - a); return z > eps ? 1 : z < - eps ? -1 : 0; }
/**
* @brief Andrew's Monotone Chain
*/
vector<point> convex_hull(vector<point> ps) {
int n = ps.size();
sort(ALL(ps), [&](point a, point b) { return make_pair(a.real(), a.imag()) < make_pair(b.real(), b.imag()); });
vector<point> ch(2 * n);
int k = 0;
for (int i = 0; i < n; ch[k ++] = ps[i ++]) // lower-hull
while (k >= 2 and ccw(ch[k - 2], ch[k - 1], ps[i]) <= 0) -- k;
for (int i = n - 2, t = k + 1; i >= 0; ch[k ++] = ps[i --]) // upper-hull
while (k >= t and ccw(ch[k - 2], ch[k - 1], ps[i]) <= 0) -- k;
ch.resize(k - 1);
return ch;
}
struct circle { point p; double r; };
struct line { point s, t; };
struct segment { point s, t; };
struct ray { point s, t; };
/**
* @note あまり小さくすると誤差で死ぬ
*/
const double eps = 1e-6;
double sq(double x) { return pow(x, 2); }
struct point { double y, x; };
point operator + (point a, point b) { return (point) { a.y + b.y, a.x + b.x }; }
point operator - (point a, point b) { return (point) { a.y - b.y, a.x - b.x }; }
point operator * (point a, double b) { return (point) { a.y * b, a.x * b }; }
point operator / (point a, double b) { return (point) { a.y / b, a.x / b }; }
point operator < (point a, point b) { return make_pair(a.y, a.x) < make_pair(b.y, b.x); }
double distance(point a, point b) { return sqrt(sq(a.y - b.y) + sq(a.x - b.x)); }
double dot(point a, point b) { return a.x * b.x + a.y * b.y; }
double cross(point a, point b) { return a.x * b.y - a.y * b.x; }
int ccw(point a, point b, point c) { double z = cross(b - a, c - a); return z > eps ? 1 : z < - eps ? -1 : 0; }
/**
* @brief segment - segment, inclusive
*/
bool does_intersect(segment const & a, segment const & b){
return ccw(a.s, a.t, b.s) * ccw(a.s, a.t, b.t) <= 0 and
ccw(b.s, b.t, a.s) * ccw(b.s, b.t, a.t) <= 0;
}
/**
* @brief point and line
*/
bool does_intersect(point a, line b) { return ccw(0, a - b.s, b.t - b.s) == 0; }
bool does_intersect(line a, point b) { return does_intersect(b, a); }
/**
* @brief line and line
*/
bool is_parallel(line a, line b) { return ccw(0, a.t - a.s, b.t - b.s) == 0; }
bool is_same(line a, line b) { return does_intersect(a.s, b) and does_intersect(a.t, b); }
/**
* @note false if two lines are the same
*/
bool does_intersect(line a, line b) {
return not is_parallel(a, b)
and not is_same(a, b);
}
point intersection(line a, line b) {
assert (does_intersect(a, b));
double p = cross(a.t - a.s, b.t - b.s);
double q = cross(a.t - a.s, a.t - b.s);
return (q / p) * (b.t - b.s) + b.s;
}
/**
* @note helper for segments and rays
*/
template <typename T, typename U>
bool does_intersect_linelikes(T const & a, U const & b) {
if (not does_intersect(to_line(a), to_line(b))) return false;
point c = intersection(to_line(a), to_line(b));
return does_intersect(c, a)
and does_intersect(c, b);
}
line to_line(segment a) {
return { a.s, a.t };
}
bool does_intersect(point a, segment b) {
return abs(cross(b.t - b.s, a - b.s)) < eps
and dot(b.t - b.s, a - b.s) > - eps
and dot(b.s - b.t, a - b.t) > - eps;
}
bool does_intersect(segment a, point b) {
return does_intersect(b, a);
}
bool is_overwraped(segment a, segment b) {
return does_intersect(a.s, b)
and does_intersect(a.t, b);
}
bool does_intersect(segment a, segment b) {
return does_intersect_linelikes(a, b);
}
point intersection(segment a, segment b) {
assert (does_intersect(a, b));
return intersection(to_line(a), to_line(b));
}
line to_line(ray a) {
return { a.s, a.t };
}
bool does_intersect(point a, ray b) {
return abs(cross(b.t - b.s, a - b.s)) < eps
and dot(b.t - b.s, a - b.s) > - eps;
}
bool does_intersect(ray a, point b) {
return does_intersect(b, a);
}
bool is_overwraped(ray a, ray b) {
return (does_intersect(a.s, b) and does_intersect(a.t, b))
or (does_intersect(b.s, a) and does_intersect(b.t, a));
}
bool does_intersect(ray a, ray b) {
return does_intersect_linelikes(a, b);
}
point intersection(ray a, ray b) {
assert (does_intersect(a, b));
return intersection(to_line(a), to_line(b));
}
struct polygon { vector<point> ps; };
segment nth_segment(polygon const & a, int i) {
int j = (i+1) % a.ps.size();
return { a.ps[i], a.ps[j] };
}
bool does_intersect(ray a, segment b) { return does_intersect_linelikes(a, b); }
bool does_intersect(segment a, ray b) { return does_intersect_linelikes(a, b); }
point intersection(ray a, segment b) { return intersection_linelikes(a, b); }
point intersection(segment a, ray b) { return intersection_linelikes(a, b); }
template <typename T>
vector<point> intersections_polygon_linelike(polygon const & a, T const & b) {
vector<point> result;
repeat (i, a.ps.size()) {
if (does_intersect(nth_segment(a, i), b)) {
result.push_back(intersection(nth_segment(a, i), b));
}
}
return result;
}
bool does_intersect(polygon const & a, ray const & b) {
return not intersections_polygon_linelike(a, b).empty();
}
bool does_intersect(polygon const & a, point const & b) {
ray c = { b, b + point(1, 0) };
return intersections_polygon_linelike(a, c).size() % 2 == 1;
}
bool does_intersect_strict(polygon const & a, point const & b) {
repeat (i, a.ps.size()) {
if (does_intersect(nth_segment(a, i), b)) {
return false; // when the point is on a segment of the polygon
}
}
return does_intersect(a, b);
}
bool does_intersect_strict(polygon const & a, segment const & b) { // the boundary is not included
vector<point> ps = intersections_polygon_linelike(a, b);
for (point p : ps) {
bool ignored = false;
if (abs(p - b.s) < eps or abs(p - b.t) < eps) {
ignored = true;
}
if (not ignored) {
for (point q : a.ps) {
if (abs(p - q) < eps) {
ignored = true; // when the intersection point is one of the vertex of the polygon
break;
}
}
}
if (not ignored) return true;
}
return false;
}