point_2d
(src/geometry/point_2d.hpp)

View this file on GitHub
Last update: 2024-11-09 01:34:39+09:00
Include: #include "src/geometry/point_2d.hpp"

Point

2次元平面上の点を扱う構造体です．

内部的には Point は complex<Real> のエイリアスです．

コンストラクタ

Point p(Real x, Real y)

座標が $(x, y)$ であるような点 p を作ります．

p の $x$ 座標へのアクセスは p.real() で， $y$ 座標へのアクセスは p.imag() でできます．

演算子として以下のものが使えます．
いずれも複素数の演算として扱われます．

Point + Point
Point - Point
Point * Point
Point / Point
Point * Real
Point / Real

また，以下のようにして入出力も行えます．

Point p;
cin >> p;
cout << p

さらにSTLに入っている complex 型の関数も使えます．

Real abs(Point p)  // pの絶対値
Real norm(Point p)  // pの2乗ノルム
Real arg(Point p)  // pの偏角
Point conj(Point p)  // pの共役複素数
Point proj(Point p)  // pのリーマン球面への射影
Point polar(Real r, Real theta)  // 極座標が(r, theta)である点

rot

Point rot(Point p, Real theta)

点 p を原点中心に角 $\mathrm{theta}$ だけ回転させた点を返します．

dot, cross

(1) Real dot(Point p1, Point p2)
(2) Real cross(Point p1, Point p2)

(1) 点 p1 と点 p2 の内積をとった値を返します．

(2) 点 p1 と点 p2 の外積をとった値を返します．

dist

Real dist(Point p1, Point p2)

点 p1 と p2 の距離を返します．

comp_x, comp_y, comp_arg

(1) bool comp_x(Point p1, Point p2)
(2) bool comp_y(Point p1, Point p2)
(3) bool comp_arg(Point p1, Point p2)

ソート等の比較関数用の関数です．

(1)は $x$ 座標の昇順にソートしたいとき，(2)は $y$ 座標の昇順にソートしたいとき，(3)は偏角の昇順にソートしたいときに使えます．

ccw

int ccw(Point a, Point b, Point c)

点 a, b に対する点 c の位置を返します．

点 a, b, c が反時計回りになる (点 c が直線 a, b の左側にある) 場合は $1$ を，
点 a, b, c が時計回りになる (点 c が直線 a, b の右側にある) 場合は $-1$ を，
点 c, a, b がこの順で同一直線上にある場合は $2$ を，
点 a, b, c がこの順で同一直線上にある場合は $-2$ を，
点 c が線分 a, b 上にある場合は $0$ を返します．

closest_pair

Real closest_pair(vector<Point> ps)

ps に含まれる点のうち，最も近い $2$ 点の距離を返します．

計算量

ps に含まれる点を $N$ 個として

$O(N \log N)$

Depends on

Required by

Verified with

Code

#pragma once
#include "../template/template.hpp"
#include "./template.hpp"
using Point = complex<Real>;
istream& operator>>(istream& is, Point& p) {
    Real a, b;
    is >> a >> b;
    p = Point(a, b);
    return is;
}
ostream& operator<<(ostream& os, const Point& p) {
    return os << p.real() << " " << p.imag();
}
Point operator*(const Point& p, const Real& d) {
    return Point(p.real() * d, p.imag() * d);
}
Point operator/(const Point& p, const Real& d) {
    return Point(p.real() / d, p.imag() / d);
}
Point rot(const Point& p, const Real& theta) {
    return p * Point(cos(theta), sin(theta));
}
Real dot(const Point& p1, const Point& p2) {
    return (conj(p1) * p2).real();
}
Real cross(const Point& p1, const Point& p2) {
    return (conj(p1) * p2).imag();
}
Real dist(const Point& p1, const Point& p2) {
    return abs(p1 - p2);
}
bool comp_x(const Point& p1, const Point& p2) {
    return eq(p1.real(), p2.real()) ? p1.imag() < p2.imag() : p1.real() < p2.real();
}
bool comp_y(const Point& p1, const Point& p2) {
    return eq(p1.imag(), p2.imag()) ? p1.real() < p2.real() : p1.imag() < p2.imag();
}
bool comp_arg(const Point& p1, const Point& p2) {
    return arg(p1) < arg(p2);
}
int ccw(const Point& a, Point b, Point c) {
    b -= a;
    c -= a;
    if(sign(cross(b, c)) == 1) return 1;
    if(sign(cross(b, c)) == -1) return -1;
    if(sign(dot(b, c)) == -1) return +2;
    if(norm(b) < norm(c)) return -2;
    return 0;
}
Real closest_pair(vector<Point> ps) {
    if((int)ps.size() <= 1) return Real(1e18);
    sort(ps.begin(), ps.end(), comp_x);
    vector<Point> memo(ps.size());
    auto func = [&](const auto& func, const int l, const int r) -> Real {
        if(r - l <= 1) return Real(1e18);
        const int m = (l + r) >> 1;
        const Real x = ps[m].real();
        Real res = min(func(func, l, m), func(func, m, r));
        inplace_merge(ps.begin() + l, ps.begin() + m, ps.begin() + r, comp_y);
        int cnt = 0;
        for(int i = l; i < r; ++i) {
            if(abs(ps[i].real() - x) >= res) continue;
            for(int j = 0; j < cnt; ++j) {
                const Point d = ps[i] - memo[cnt - j - 1];
                if(d.imag() >= res) break;
                res = min(res, abs(d));
            }
            memo[cnt++] = ps[i];
        }
        return res;
    };
    return func(func, 0, (int)ps.size());
}

#line 2 "src/template/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<long long, long long>;
#define rep(i, a, b) for(long long i = (a); i < (b); ++i)
#define rrep(i, a, b) for(long long i = (a); i >= (b); --i)
constexpr long long inf = 4e18;
struct SetupIO {
    SetupIO() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout << fixed << setprecision(30);
    }
} setup_io;
#line 3 "src/geometry/template.hpp"
using Real = long double;
constexpr Real EPS = Real(1e-8), PI = 3.141592653589793238462643383279L;
int sign(const Real& r) {
    if(r <= -EPS) return -1;
    if(r >= +EPS) return +1;
    return 0;
}
bool eq(const Real& a, const Real& b) {
    return sign(a - b) == 0;
}
#line 4 "src/geometry/point_2d.hpp"
using Point = complex<Real>;
istream& operator>>(istream& is, Point& p) {
    Real a, b;
    is >> a >> b;
    p = Point(a, b);
    return is;
}
ostream& operator<<(ostream& os, const Point& p) {
    return os << p.real() << " " << p.imag();
}
Point operator*(const Point& p, const Real& d) {
    return Point(p.real() * d, p.imag() * d);
}
Point operator/(const Point& p, const Real& d) {
    return Point(p.real() / d, p.imag() / d);
}
Point rot(const Point& p, const Real& theta) {
    return p * Point(cos(theta), sin(theta));
}
Real dot(const Point& p1, const Point& p2) {
    return (conj(p1) * p2).real();
}
Real cross(const Point& p1, const Point& p2) {
    return (conj(p1) * p2).imag();
}
Real dist(const Point& p1, const Point& p2) {
    return abs(p1 - p2);
}
bool comp_x(const Point& p1, const Point& p2) {
    return eq(p1.real(), p2.real()) ? p1.imag() < p2.imag() : p1.real() < p2.real();
}
bool comp_y(const Point& p1, const Point& p2) {
    return eq(p1.imag(), p2.imag()) ? p1.real() < p2.real() : p1.imag() < p2.imag();
}
bool comp_arg(const Point& p1, const Point& p2) {
    return arg(p1) < arg(p2);
}
int ccw(const Point& a, Point b, Point c) {
    b -= a;
    c -= a;
    if(sign(cross(b, c)) == 1) return 1;
    if(sign(cross(b, c)) == -1) return -1;
    if(sign(dot(b, c)) == -1) return +2;
    if(norm(b) < norm(c)) return -2;
    return 0;
}
Real closest_pair(vector<Point> ps) {
    if((int)ps.size() <= 1) return Real(1e18);
    sort(ps.begin(), ps.end(), comp_x);
    vector<Point> memo(ps.size());
    auto func = [&](const auto& func, const int l, const int r) -> Real {
        if(r - l <= 1) return Real(1e18);
        const int m = (l + r) >> 1;
        const Real x = ps[m].real();
        Real res = min(func(func, l, m), func(func, m, r));
        inplace_merge(ps.begin() + l, ps.begin() + m, ps.begin() + r, comp_y);
        int cnt = 0;
        for(int i = l; i < r; ++i) {
            if(abs(ps[i].real() - x) >= res) continue;
            for(int j = 0; j < cnt; ++j) {
                const Point d = ps[i] - memo[cnt - j - 1];
                if(d.imag() >= res) break;
                res = min(res, abs(d));
            }
            memo[cnt++] = ps[i];
        }
        return res;
    };
    return func(func, 0, (int)ps.size());
}

point_2d (src/geometry/point_2d.hpp)