結果

問題 No.3154 convex polygon judge
ユーザー 遭難者
提出日時 2025-05-20 21:46:50
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 143 ms / 2,000 ms
コード長 16,642 bytes
コンパイル時間 3,720 ms
コンパイル使用メモリ 301,696 KB
実行使用メモリ 22,276 KB
最終ジャッジ日時 2025-05-20 21:46:57
合計ジャッジ時間 6,173 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 44
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ld = long double;
#undef long
#define long long long
#define ll long
#define vec vector
#define rep(i, n) for (long i = 0; i < n; i++)
#define all(a) begin(a), end(a)
#define sz(a) (int)(a).size()
template <typename T>
bool chmin(T &x, T y)
{
    if (y < x)
    {
        x = y;
        return true;
    }
    return false;
}
template <typename T>
bool chmax(T &x, T y)
{
    if (x < y)
    {
        x = y;
        return true;
    }
    return false;
}
template <typename T>
ostream &operator<<(ostream &os, vector<T> a)
{
    const int n = a.size();
    rep(i, n)
    {
        os << a[i];
        if (i + 1 != n)
            os << " ";
    }
    return os;
}

using R = ld;
using point = std::complex<R>;
using arrow = point;
const R EPS(1e-10), PI(acosl(-1));

inline bool eq(const R &a, const R &b) { return abs(b - a) < EPS; }
inline bool same_point(const point &a, const point &b) { return abs(b - a) < EPS; }
/*
        sign of x
        -1: x < 0
         0: x == 0
         1: x > 0
*/
inline int sgn(const R &x) { return abs(x) < EPS ? 0 : (x < 0 ? -1 : 1); }
/*
        sign of (a-b)
        -1: a < b
         0: a == b
         1: a > b
*/
inline int compare(const R &a, const R &b) { return eq(a, b) ? 0 : a < b ? -1
                                                                         : 1; }

std::istream &operator>>(std::istream &is, point &p)
{
    R a, b;
    is >> a >> b;
    p = point(a, b);
    return is;
}
std::ostream &operator<<(std::ostream &os, point &p) { return os << '(' << p.real() << ", " << p.imag() << ')'; }

// rotate point 'p' for counter clockwise direction
point rotate(const point &p, const R &theta)
{
    return point(cosl(theta) * p.real() - sinl(theta) * p.imag(), sinl(theta) * p.real() + cosl(theta) * p.imag());
}

R radian_to_degree(const R &r) { return (r * 180.0 / PI); }
R degree_to_radian(const R &d) { return (d * PI / 180.0); }

// get angle a-b-c (<pi)
R get_angle(const point &a, const point &b, const point &c)
{
    const point v(a - b), w(c - b);
    R theta = abs(atan2l(w.imag(), w.real()) - atan2l(v.imag(), v.real()));
    return std::min(theta, 2 * PI - theta);
}

namespace std
{
    bool operator<(const point &a, const point &b)
    {
        return a.real() != b.real() ? a.real() < b.real() : a.imag() < b.imag();
    }
} // namespace std

struct segment;
struct line
{
    point a, b;
    line() = default;
    line(const point &a, const point &b) : a(a), b(b) {}
    // Ax + By + C = 0
    line(const R &A, const R &B, const R &C)
    {
        if (eq(A, 0))
        {
            assert(!eq(B, 0));
            a = point(0, -C / B), b = point(1, -(A + C) / B);
        }
        else
        {
            a = point(-C / A, 0), b = point(-(B + C) / A, 1);
        }
    }
    explicit line(const segment &seg);
    friend std::ostream &operator<<(std::ostream &os, const line &ln)
    {
        return os << '(' << ln.a << " -- " << ln.b << ')';
    }
    friend std::istream &operator>>(std::istream &is, line &a) { return is >> a.a >> a.b; }
};
struct segment
{
    point a, b;
    segment() = default;
    segment(const point &a, const point &b) : a(a), b(b) {}
    explicit segment(const line &ln) : a(ln.a), b(ln.b) {}
    friend std::ostream &operator<<(std::ostream &os, const segment &seg)
    {
        return os << '[' << seg.a << " -- " << seg.b << ']';
    }
    friend std::istream &operator>>(std::istream &is, segment &a) { return is >> a.a >> a.b; }
};
line::line(const segment &seg) : a(seg.a), b(seg.b) {}

struct circle
{
    point center;
    R radius;
    circle() = default;
    circle(const point &center, const R &radius) : center(center), radius(radius) {}
    friend std::ostream &operator<<(std::ostream &os, const circle &c)
    {
        return os << '(' << c.center << ", " << c.radius << ')';
    }
    friend std::istream &operator>>(std::istream &is, circle &c) { return is >> c.center >> c.radius; }
};

using points = std::vector<point>;
using polygon = std::vector<point>;
using segments = std::vector<segment>;
using lines = std::vector<line>;
using circles = std::vector<circle>;

// 内積
R cross(const point &a, const point &b) { return real(a) * imag(b) - imag(a) * real(b); }
// 外積
R dot(const point &a, const point &b) { return real(a) * real(b) + imag(a) * imag(b); }

// 点 a,b から見て c がどの位置にいるか
enum CCW
{
    ONLINE_FRONT = -2,     // a,b,c が一直線上
    CLOCKWISE = -1,        // c が a,b から時計回り側
    ON_SEGMENT = 0,        // a,c,b が一直線上
    COUNTER_CLOCKWISE = 1, // c が a,b から反時計回り側
    ONLINE_BACK = 2,       // c,a,b が一直線上
};
int ccw(const point &a, point b, point c)
{
    b -= a, c -= a;
    const R crs_b_c = cross(b, c);
    if (crs_b_c > EPS)
        return CCW::COUNTER_CLOCKWISE;
    if (crs_b_c < -EPS)
        return CCW::CLOCKWISE;
    if (dot(b, c) < -EPS)
        return CCW::ONLINE_BACK;
    if (norm(b) + EPS < norm(c))
        return CCW::ONLINE_FRONT;
    return CCW::ON_SEGMENT;
}

bool parallel(const arrow &a, const arrow &b) { return eq(cross(a, b), R(0)); }
bool parallel(const line &a, const line &b) { return parallel(a.b - a.a, b.b - b.a); }
bool parallel(const line &a, const segment &b) { return parallel(a.b - a.a, b.b - b.a); }
bool parallel(const segment &a, const line &b) { return parallel(a.b - a.a, b.b - b.a); }
bool parallel(const segment &a, const segment &b) { return parallel(a.b - a.a, b.b - b.a); }

bool orthogonal(const arrow &a, const arrow &b) { return eq(dot(a, b), R(0)); }
bool orthogonal(const line &a, const line &b) { return orthogonal(a.b - a.a, b.b - b.a); }
bool orthogonal(const line &a, const segment &b) { return orthogonal(a.b - a.a, b.b - b.a); }
bool orthogonal(const segment &a, const line &b) { return orthogonal(a.b - a.a, b.b - b.a); }
bool orthogonal(const segment &a, const segment &b) { return orthogonal(a.b - a.a, b.b - b.a); }

point projection(const line &l, const point &p)
{
    return l.a + (l.a - l.b) * dot(p - l.a, l.a - l.b) / norm(l.a - l.b);
}
point projection(const segment &s, const point &p) { return projection(line(s), p); }

point reflection(const line &l, const point &p) { return projection(l, p) * R(2) - p; }
point reflection(const segment &s, const point &p) { return projection(line(s), p); }

R distance(const point &p, const point &q);
R distance(const line &l, const point &p);
int number_of_common_tangents(const circle &c1, const circle &c2)
{
    const R r1 = std::min(c1.radius, c2.radius), r2 = std::max(c1.radius, c2.radius), d = distance(c1.center, c2.center);
    int com = compare(r1 + r2, d);
    return com == 1 ? compare(d + r1, r2) + 1 : 3 - com;
}

// number of common points (-1: infinite)
int intersect(const line &l, const point &p) { return int(abs(ccw(l.a, l.b, p)) != 1); }
int intersect(const point &p, const line &l) { return intersect(l, p); }
int intersect(const line &l, const line &m)
{
    if (intersect(l, m.a) && intersect(l, m.b))
        return -1;
    return int(!parallel(l, m));
}
int intersect(const segment &s, const point &p) { return int(ccw(s.a, s.b, p) == CCW::ON_SEGMENT); }
int intersect(const point &p, const segment &s) { return intersect(s, p); }
int intersect(const line &l, const segment &s)
{
    if (intersect(l, s.a) && intersect(l, s.b))
        return -1;
    return ccw(l.a, l.b, s.a) * ccw(l.a, l.b, s.b) != 1;
}
int intersect(const segment &s, const line &l) { return intersect(l, s); }
int intersect(const circle &c, const line &l)
{
    R d = c.radius - distance(l, c.center);
    return abs(d) < EPS ? 1 : d > 0. ? 2
                                     : 0;
}
int intersect(const line &l, const circle &c) { return intersect(c, l); }
int intersect(const circle &c, const point &p) { return int(eq(c.radius, distance(c.center, p))); }
int intersect(const point &p, const circle &c) { return intersect(c, p); }
int intersect(const segment &s, const segment &t)
{
    if (same_point(s.a, s.b))
        return intersect(t, s.a);
    if (intersect(line(s), t.a) && intersect(line(s), t.b) && std::max(std::min(s.a, s.b), std::min(t.a, t.b)) < std::min(std::max(s.a, s.b), std::max(t.a, t.b)))
        return -1;
    return int(ccw(s.a, s.b, t.a) * ccw(s.a, s.b, t.b) <= 0 && ccw(t.a, t.b, s.a) * ccw(t.a, t.b, s.b) <= 0);
}
int intersect(const circle &c, const segment &s)
{
    const point h = projection(s, c.center);
    const int c0 = compare(distance(h, c.center), c.radius);
    if (c0 == 1)
        return 0;
    if (c0 == 0)
        return intersect(s, h);
    const int c1 = compare(distance(c.center, s.a), c.radius), c2 = compare(distance(c.center, s.b), c.radius);
    if (std::min(c1, c2) == -1)
        return int(std::max(c1, c2) >= 0);
    return intersect(s, h) ? 2 : 0;
}
int intersect(const segment &s, const circle &c) { return intersect(c, s); }
int intersect(const circle &c1, const circle &c2) { return 2 - abs(2 - number_of_common_tangents(c1, c2)); }

// distance of two shapes
R distance(const point &a, const point &b) { return abs(a - b); }
R distance(const line &l, const point &p) { return distance(p, projection(l, p)); }
R distance(const point &p, const line &l) { return distance(l, p); }
R distance(const line &l, const line &m) { return parallel(l, m) ? distance(l, m.a) : 0; }
R distance(const segment &s, const point &p)
{
    const point r = projection(s, p);
    return intersect(s, r) ? distance(r, p) : std::min(distance(s.a, p), distance(s.b, p));
}
R distance(const point &p, const segment &s) { return distance(s, p); }
R distance(const segment &a, const segment &b)
{
    if (intersect(a, b))
        return R(0);
    return std::min({distance(a, b.a), distance(a, b.b), distance(b, a.a), distance(b, a.b)});
}
R distance(const line &l, const segment &s)
{
    if (intersect(l, s))
        return 0;
    return std::min(distance(l, s.a), distance(l, s.b));
}
R distance(const segment &s, const line &l) { return distance(l, s); }
R distance(const circle &c, const point &p) { return abs(distance(c.center, p) - c.radius); }
R distance(const point &p, const circle &c) { return distance(c, p); }
R distance(const circle &c, const line &l) { return std::max(R(0), distance(l, c.center) - c.radius); }
R distance(const line &l, const circle &c) { return distance(c, l); }
R distance(const circle &c1, const circle &c2)
{
    const R d = distance(c1.center, c2.center);
    if (d > c1.radius + c2.radius)
        return d - c1.radius - c2.radius;
    if (d < abs(c1.radius - c2.radius))
        return abs(c1.radius - c2.radius) - d;
    return R(0);
}
R distance(const circle &c, const segment &s)
{
    const point p = projection(s, c.center);
    const R dist_min =
        intersect(s, p) ? distance(c.center, p) : std::min(distance(c.center, s.a), distance(c.center, s.b));
    if (dist_min > c.radius)
        return dist_min - c.radius;
    const R dist_max = std::max(distance(c.center, s.a), distance(c.center, s.b));
    return dist_max < c.radius ? c.radius - dist_max : R(0);
}
R distance(const segment &s, const circle &c) { return distance(c, s); }

point crosspoint(const line &l, const line &m)
{
    R A = cross(l.b - l.a, m.b - m.a);
    R B = cross(l.b - l.a, l.b - m.a);
    if (eq(A, 0.))
        return m.a;
    return m.a + (m.b - m.a) * B / A;
}
point crosspoint(const segment &s, const segment &t) { return crosspoint(line(s), line(t)); }
point crosspoint(const segment &s, const line &l) { return crosspoint(line(s), l); }
point crosspoint(const line &l, const segment &s) { return crosspoint(l, line(s)); }
points crosspoints(const circle &c, const line &l)
{
    const point pr = projection(l, c.center);
    const R square = c.radius * c.radius - norm(pr - c.center);
    switch (sgn(square))
    {
    case 0:
        return points{pr};
    case -1:
        return points(0);
    }
    const arrow v = (l.b - l.a) / abs(l.b - l.a) * sqrtl(square);
    return points{pr - v, pr + v};
}
points crosspoints(const line &l, const circle &c) { return crosspoints(c, l); }
points crosspoints(const circle &c, const segment &s)
{
    points ret;
    for (const auto &pt : crosspoints(c, line(s)))
        if (intersect(s, pt))
            ret.push_back(pt);
    return ret;
}
points crosspoints(const segment &s, const circle &c) { return crosspoints(c, s); }
points crosspoints(const circle &c1, const circle &c2)
{
    R d = abs(c1.center - c2.center);
    if (compare(d, c1.radius + c2.radius) == 1)
        return points(0);
    if (compare(d, abs(c1.radius - c2.radius)) == -1)
        return points(0);
    bool one_crosspoint = false;
    if (eq(d, c1.radius + c2.radius) || eq(d, abs(c1.radius - c2.radius)))
        one_crosspoint = true;
    const R alpha =
        acosl((c1.radius * c1.radius + d * d - c2.radius * c2.radius) / (2 * c1.radius * d)); // cosine theorem
    const R beta = std::arg(c2.center - c1.center);
    if (one_crosspoint)
        return points{c1.center + std::polar(c1.radius, beta + alpha)};
    return points{c1.center + std::polar(c1.radius, beta + alpha), c1.center + std::polar(c1.radius, beta - alpha)};
}

points tangent_points(const circle &c, const point &p)
{
    const R square = norm(c.center - p) - c.radius * c.radius;
    switch (sgn(square))
    {
    case 0:
        return points{p};
    case -1:
        return points{};
    }
    return crosspoints(c, circle(p, sqrtl(square)));
}

// common tangents of two circles
lines tangents(circle c1, circle c2)
{
    lines ret;
    if (c1.radius < c2.radius)
        std::swap(c1, c2);
    const R g = distance(c1.center, c2.center);
    if (!sgn(g))
        return ret;
    const arrow u = (c2.center - c1.center) / g;
    const arrow v = rotate(u, PI * 0.5);
    for (const int &s : {-1, 1})
    {
        const R h = (c1.radius + s * c2.radius) / g;
        if (eq(1 - h * h, 0))
        {
            ret.emplace_back(c1.center + u * c1.radius, c1.center + (u + v) * c1.radius);
        }
        else if (1 - h * h > 0)
        {
            const point uu = u * h, vv = v * sqrtl(1 - h * h);
            ret.emplace_back(c1.center + (uu + vv) * c1.radius, c2.center - (uu + vv) * c2.radius * R(s));
            ret.emplace_back(c1.center + (uu - vv) * c1.radius, c2.center - (uu - vv) * c2.radius * R(s));
        }
    }
    return ret;
}

bool is_convex(const polygon &p, bool pi_is_ok = true)
{
    int n = (int)p.size();
    if (pi_is_ok)
    {
        for (int i = 0; i < n; i++)
            if (ccw(p[i], p[(i + 1) % n], p[(i + 2) % n]) == -1)
                return false;
    }
    else
    {
        for (int i = 0; i < n; i++)
            if (ccw(p[i], p[(i + 1) % n], p[(i + 2) % n]) != 1)
                return false;
    }
    return true;
}

polygon convex_hull(polygon &p, bool vertices_on_edge_remain = true)
{
    int n = (int)p.size(), k = 0;
    if (n <= 2)
        return p;
    sort(p.begin(), p.end());
    points ch(2 * n);
    if (vertices_on_edge_remain)
    {
        for (int i = 0; i < n; ch[k++] = p[i++])
            while (k >= 2 && ccw(ch[k - 2], ch[k - 1], p[i]) == -1)
                --k;
        for (int i = n - 2, t = k + 1; i >= 0; ch[k++] = p[i--])
            while (k >= t && ccw(ch[k - 2], ch[k - 1], p[i]) == -1)
                --k;
    }
    else
    {
        for (int i = 0; i < n; ch[k++] = p[i++])
            while (k >= 2 && ccw(ch[k - 2], ch[k - 1], p[i]) != 1)
                --k;
        for (int i = n - 2, t = k + 1; i >= 0; ch[k++] = p[i--])
            while (k >= t && ccw(ch[k - 2], ch[k - 1], p[i]) != 1)
                --k;
    }
    ch.resize(k - 1);
    return ch;
}

// 凸多角形 U を直線 a-b で切断し、左側に残る部分多角形（左半平面）を返す
// (i.e. forall p \in (returned polygon), ccw(a, b, p) != -1)
polygon convex_cut(const polygon &U, const point &a, const point &b)
{
    polygon ret;
    const line l(a, b);
    for (int i = 0; i < int(U.size()); i++)
    {
        const point &now = U[i], &nxt = U[(i + 1) % int(U.size())];
        if (ccw(l.a, l.b, now) != -1)
            ret.push_back(now);
        if (ccw(l.a, l.b, now) * ccw(l.a, l.b, nxt) == -1)
            ret.push_back(crosspoint(line(now, nxt), l));
    }
    return ret;
}

void solve()
{
    int n;
    cin >> n;
    vec<point> a(n);
    rep(i, n)
    {
        ld x, y;
        cin >> x >> y;
        a[i] = {x, y};
    }
    auto res = convex_hull(a, false);
    cout << (sz(res) == n ? "Yes" : "No") << endl;
}
int main()
{
    cin.tie(0)->sync_with_stdio(0), cout.tie(0);
    cout << fixed << setprecision(20);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
}
0