結果

問題 No.3154 convex polygon judge
コンテスト
ユーザー siganai
提出日時 2025-05-20 21:29:53
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 84 ms / 2,000 ms
コード長 22,487 bytes
コンパイル時間 2,969 ms
コンパイル使用メモリ 234,836 KB
実行使用メモリ 9,268 KB
最終ジャッジ日時 2025-05-20 21:30:03
合計ジャッジ時間 4,931 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 44
権限があれば一括ダウンロードができます

ソースコード

diff # 

#line 1 "main.cpp"
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include <debug.hpp>
#define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (static_cast<void>(0))
#endif
//#pragma GCC target("avx,avx2")
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pll = pair<ll,ll>;
using pii = pair<int,int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vvvl = vector<vvl>;
using vul = vector<ull>;
using vpii = vector<pii>;
using vvpii = vector<vpii>;
using vpll = vector<pll>;
using vs = vector<string>;
template<class T> using pq = priority_queue<T,vector<T>, greater<T>>;
#define overload4(_1, _2, _3, _4, name, ...) name
#define overload3(a,b,c,name,...) name
#define rep1(n) for (ll UNUSED_NUMBER = 0; UNUSED_NUMBER < (n); ++UNUSED_NUMBER)
#define rep2(i, n) for (ll i = 0; i < (n); ++i)
#define rep3(i, a, b) for (ll i = (a); i < (b); ++i)
#define rep4(i, a, b, c) for (ll i = (a); i < (b); i += (c))
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep1(n) for(ll i = (n) - 1;i >= 0;i--)
#define rrep2(i,n) for(ll i = (n) - 1;i >= 0;i--)
#define rrep3(i,a,b) for(ll i = (b) - 1;i >= (a);i--)
#define rrep4(i,a,b,c) for(ll i = (a) + (((b)-(a)-1) / (c) - (((b)-(a)-1) % (c) && (((b)-(a)-1) ^ c) < 0)) * (c);i >= (a);i -= c)
#define rrep(...) overload4(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__)
#define all1(i) begin(i) , end(i)
#define all2(i,a) begin(i) , begin(i) + a
#define all3(i,a,b) begin(i) + a , begin(i) + b
#define all(...) overload3(__VA_ARGS__, all3, all2, all1)(__VA_ARGS__)
#define sum(...) accumulate(all(__VA_ARGS__),0LL)
template<class T> bool chmin(T &a, const T &b){ if(a > b){ a = b; return 1; } else return 0; }
template<class T> bool chmax(T &a, const T &b){ if(a < b){ a = b; return 1; } else return 0; }
template<class T> auto min(const T& a){return *min_element(all(a));}
template<class T> auto max(const T& a){return *max_element(all(a));}
template<class... Ts> void in(Ts&... t);
#define INT(...) int __VA_ARGS__; in(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__; in(__VA_ARGS__)
#define STR(...) string __VA_ARGS__; in(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__; in(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__; in(__VA_ARGS__)
#define LD(...) ld __VA_ARGS__; in(__VA_ARGS__)
#define VEC(type, name, size) vector<type> name(size); in(name)
#define VV(type, name, h, w) vector<vector<type>> name(h, vector<type>(w)); in(name)
ll intpow(ll a, ll b){ll ans = 1; while(b){if(b & 1) ans *= a; a *= a; b /= 2;} return ans;}
ll modpow(ll a, ll b, ll p){ ll ans = 1; a %= p;if(a < 0) a += p;while(b){ if(b & 1) (ans *= a) %= p; (a *= a) %= p; b /= 2; } return ans; }
bool is_clamp(ll val,ll low,ll high) {return low <= val && val < high;}
void Yes() {cout << "Yes\n";return;}
void No() {cout << "No\n";return;}
void YES() {cout << "YES\n";return;}
void NO() {cout << "NO\n";return;}
template <typename T>
T floor(T a, T b) {return a / b - (a % b && (a ^ b) < 0);}
template <typename T>
T ceil(T x, T y) {return floor(x + y - 1, y);}
template <typename T>
T bmod(T x, T y) {return x - y * floor(x, y);}
template <typename T>
pair<T, T> divmod(T x, T y) {T q = floor(x, y);return {q, x - q * y};}
namespace IO{
#define VOID(a) decltype(void(a))
struct setting{ setting(){cin.tie(nullptr); ios::sync_with_stdio(false);fixed(cout); cout.precision(15);}} setting;
template<int I> struct P : P<I-1>{};
template<> struct P<0>{};
template<class T> void i(T& t){ i(t, P<3>{}); }
void i(vector<bool>::reference t, P<3>){ int a; i(a); t = a; }
template<class T> auto i(T& t, P<2>) -> VOID(cin >> t){ cin >> t; }
template<class T> auto i(T& t, P<1>) -> VOID(begin(t)){ for(auto&& x : t) i(x); }
template<class T, size_t... idx> void ituple(T& t, index_sequence<idx...>){in(get<idx>(t)...);}
template<class T> auto i(T& t, P<0>) -> VOID(tuple_size<T>{}){ituple(t, make_index_sequence<tuple_size<T>::value>{});} 
#undef VOID
}
#define unpack(a) (void)initializer_list<int>{(a, 0)...}
template<class... Ts> void in(Ts&... t){ unpack(IO :: i(t)); }
#undef unpack
constexpr long double PI = 3.141592653589793238462643383279L;
template <class F> struct REC {
    F f;
    REC(F &&f_) : f(forward<F>(f_)) {}
    template <class... Args> auto operator()(Args &&...args) const { return f(*this, forward<Args>(args)...); }};

constexpr int mod = 998244353;
//constexpr int mod = 1000000007;

#line 2 "library/geometry/pointbase.hpp"
template <typename R>
struct PointBase {
    using P = PointBase;
    R x, y;
    PointBase() : x(0), y(0) {}
    PointBase(R _x, R _y) : x(_x), y(_y) {}
    template <typename T, typename U>
    PointBase(const pair<T, U>& p) : x(p.first), y(p.second) {}
    P operator+(const P& r) const { return {x + r.x, y + r.y}; }
    P operator-(const P& r) const { return {x - r.x, y - r.y}; }
    P operator*(R r) const { return {x * r, y * r}; }
    P operator/(R r) const { return {x / r, y / r}; }
    P& operator+=(const P& r) { return (*this) = (*this) + r; }
    P& operator-=(const P& r) { return (*this) = (*this) - r; }
    P& operator*=(R r) { return (*this) = (*this) * r; }
    P& operator/=(R r) { return (*this) = (*this) / r; }
    bool operator<(const P& r) const { return x != r.x ? x < r.x : y < r.y; }
    bool operator>(const P& r) const { return x != r.x ? x > r.x : y > r.y; }
    bool operator==(const P& r) const { return x == r.x and y == r.y; }
    bool operator!=(const P& r) const { return !((*this) == r); }
    P rotate(long double rad) const {
        static_assert(!is_integral<R>::value);
        return {x * cos(rad) - y * sin(rad), x * sin(rad) + y * cos(rad)};
    }
    P conj() const {return {x,-y};}
    R real() const { return x; }
    R imag() const { return y; }
    friend R real(const P& p) { return p.x; }
    friend R imag(const P& p) { return p.y; }
    friend R dot(const P& l, const P& r) { return l.x * r.x + l.y * r.y; }
    friend R cross(const P& l, const P& r) { return l.x * r.y - l.y * r.x; }
    friend long double abs(const P& p) { return sqrt(p.x * p.x + p.y * p.y); }
    friend R norm(const P& p) { return p.x * p.x + p.y * p.y; }
    friend long double arg(const P& p) { return atan2(p.y, p.x); }
    friend istream& operator>>(istream& is, P& p) {
        R a, b;
        is >> a >> b;
        p = P{a, b};
        return is;
    }
    friend ostream& operator<<(ostream& os, const P& p) {
        return os << p.x << " " << p.y;
    }
};
#line 3 "library/geometry/geometry-base.hpp"
using Real = long double;
using Point = PointBase<Real>;
long double EPS = 1e-11;
inline int sign(const Real &r) { return r <= -EPS ? -1 : r >= EPS ? 1 : 0; }
bool equals(Real a, Real b) { return fabs(b - a) < EPS; }
Real radian_to_degree(Real r) { return (r * 180.0 / PI); }
Real degree_to_radian(Real d) { return (d * PI / 180.0); }
int ccw(const Point &a,Point b,Point c) {
    b = b - a, c = c - a;
    if(cross(b,c) > EPS) return +1;  //反時計回り
    if(cross(b,c) < -EPS) return -1; //時計回り
    if(dot(b,c) < -EPS) return +2;      //b-a-c
    if(norm(b) < norm(c)) return -2; //a-b-c
    return 0;                        //a-c-b
}
// a-bベクトルとb-cベクトルのなす角
long double get_angle(const Point &a,const Point &b,const Point &c) {
    const Point v(b - a), w(c - b);
    long double alpha = arg(v), beta = arg(w);
    if(alpha > beta) swap(alpha,beta);
    long double theta = beta - alpha;
    return min(theta,2 * acosl(-1) - theta);
}
struct Circle {
    Point p;
    Real r;
    Circle() = default;
    Circle(Point _p,Real _r):p(_p),r(_r){}
};
struct Line {
    Point a, b;
    Line() = default;
    Line(Point a, Point b) : a(a), b(b) {}
    Line(Real A, Real B, Real C) // Ax + By = C
    {
        if(equals(A,0.0)) a = Point(0, C / B), b = Point(1, C / B);
        else if((equals(B,0.0))) a = Point(C / A, 0), b = Point(C / A, 1);
        else a = Point(0, C / B), b = Point(C / A, 0);
    }
    friend ostream &operator<<(ostream &os, Line &p) {
        return os << p.a << " to " << p.b;
    }
    friend istream &operator>>(istream &is, Line &a) {
        return is >> a.a >> a.b;
    }
};
struct Segment : Line {
    Segment() = default;
    Segment(Point a, Point b) : Line(a, b) {}
};
bool parallel(const Line &a, const Line &b) {
    return equals(cross(a.b - a.a, b.b - b.a),0.0);
}
bool orthogonal(const Line &a, const Line &b) {
    return equals(dot(a.a - a.b, b.a - b.b),0.0);
}
Point projection(const Line &l, const Point &p) {
    Real t = dot(p - l.a, l.a - l.b) / norm(l.a - l.b);
    return l.a + (l.a - l.b) * t;
}
Point reflection(const Line &l, const Point &p) {
    return p + (projection(l, p) - p) * 2.0;
}
using Points = vector<Point>;
using Polygon = vector<Point>;
using Lines = vector<Line>;
using Segments = vector<Segment>;
using Circles = vector<Circle>;
#line 3 "library/geometry/intersect.hpp"
bool intersect(const Line &l, const Point &p) {
    return abs(ccw(l.a, l.b, p)) != 1;
}
bool intersect(const Line &l, const Line &m) {
    return abs(cross(l.b - l.a, m.b - m.a)) > EPS || abs(cross(l.b - l.a, m.b - l.a)) < EPS;
}
bool intersect(const Segment &s, const Point &p) {
    return ccw(s.a, s.b, p) == 0;
}
bool intersect(const Line &l, const Segment &s) {
    return cross(l.b - l.a, s.a - l.a) * cross(l.b - l.a, s.b - l.a) < EPS;
}
bool intersect(const Segment &s,const Line &l) {
    return intersect(l,s);   
}
Real distance(const Line &l, const Point &p);
bool intersect(const Circle &c, const Line &l) {
    return abs(c.p - projection(l, c.p)) <= c.r + EPS;
}
bool intersect(const Circle &c, const Point &p) {
    return abs(abs(p - c.p) - c.r) < EPS;
}
bool intersect(const Segment &s, const Segment &t) {
    return 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 &l) {
    if (norm(projection(l, c.p) - c.p) - c.r * c.r > EPS) return 0;
    auto d1 = abs(c.p - l.a), d2 = abs(c.p - l.b);
    if (d1 < c.r + EPS && d2 < c.r + EPS) return 0;
    if (d1 < c.r - EPS && d2 > c.r + EPS || d1 > c.r + EPS && d2 < c.r - EPS)
        return 1;
    const Point h = projection(l, c.p);
    if (dot(l.a - h, l.b - h) < 0) return 2;
    return 0;
}
int intersect(Circle c1,Circle c2) {
    if(c1.r < c2.r) swap(c1,c2);
    Real d = abs(c1.p - c2.p);
    if(c1.r + c2.r < d) return 4;   //円が離れている
    if(equals(c1.r + c2.r,d)) return 3; //円の外部と外部が接している
    if(c1.r - c2.r < d) return 2;   //円が交わっている
    if(equals(c1.r - c2.r,d)) return 1; //一方の円の内部ともう一方の円の外部と接している
    return 0;                       //一方の円の内部にもう一方の円がある
}
#line 4 "library/geometry/distance.hpp"
Real distance(const Point &a, const Point &b) { return abs(a - b); }
Real distance(const Line &l, const Point &p) {
    return abs(p - projection(l, p));
}
Real distance(const Line &l, const Line &m) {
    return intersect(l, m) ? 0 : distance(l, m.a);
}
Real distance(const Segment &s, const Point &p) {
    Point r = projection(s, p);
    if (intersect(s, r)) return abs(r - p);
    return min(abs(s.a - p), abs(s.b - p));
}
Real distance(const Segment &a, const Segment &b) {
    if (intersect(a, b)) return 0;
    return min({distance(a, b.a), distance(a, b.b), distance(b, a.a), distance(b, a.b)});
}
Real distance(const Line &l, const Segment &s) {
    if (intersect(l, s)) return 0;
    return min(distance(l, s.a), distance(l, s.b));
}
#line 4 "library/geometry/crosspoint.hpp"
Point crosspoint(const Line &l, const Line &m) {
    Real A = cross(l.b - l.a, m.b - m.a);
    Real B = cross(l.b - l.a, l.b - m.a);
    if(equals(abs(A), 0.0) && equals(abs(B), 0.0)) return m.a;
    return m.a + (m.b - m.a) * B / A;
}
Point crosspoint(const Segment &l, const Segment &m) {
    return crosspoint(Line(l), Line(m));
}
pair<Point,Point> crosspoint(const Circle &c, const Line &l) {
    Point pr = projection(l, c.p);
    Point e = (l.b - l.a) / abs(l.b - l.a);
    if(equals(distance(l, c.p), c.r)) return {pr, pr};
    Real base = sqrt(c.r * c.r - norm(pr - c.p));
    return {pr - e * base, pr + e * base};
}
pair<Point, Point> crosspoint(const Circle &c, const Segment &l) {
    Line aa = Line(l.a, l.b);
    if (intersect(c, l) == 2) return crosspoint(c, aa);
    auto ret = crosspoint(c, aa);
    if (dot(l.a - ret.first, l.b - ret.first) < 0)
        ret.second = ret.first;
    else
        ret.first = ret.second;
    return ret;
}
pair<Point,Point> crosspoint(const Circle &c1,const Circle &c2) {
    Real d = abs(c1.p - c2.p);
    Real x = (c1.r * c1.r + d * d - c2.r * c2.r) / (2 * c1.r * d);
    if (abs(x) > 1) x = (x > 0 ? 1.0 : -1.0);
    Real a = acos(x);
    Real t = atan2(c2.p.imag() - c1.p.imag(), c2.p.real() - c1.p.real());
    Point p1 = c1.p + Point(cos(t + a) * c1.r, sin(t + a) * c1.r);
    Point p2 = c1.p + Point(cos(t - a) * c1.r, sin(t - a) * c1.r);
    return {p1, p2};
}
#line 5 "library/geometry/Polygon.hpp"
template<typename T>
bool is_convex(const vector<PointBase<T>> &p) {
    int n = (int)p.size();
    for (int i = 0; i < n; i++) {
        if (ccw(p[(i + n - 1) % n], p[i], p[(i + 1) % n]) == -1) return false;
    }
    return true;
}
// allow_180=true で同一座標点があるとこわれる
// full なら I[0] が sorted で min になる
template <typename T, bool allow_180 = false>
vector<int> convex_full(vector<PointBase<T>> &XY, string mode = "full", bool sorted = false) {
    assert(mode == "full" || mode == "lower" || mode == "upper");
    int N = XY.size();
    if (N == 1) return {0};
    if (N == 2) {
        if (XY[0] < XY[1]) return {0, 1};
        if (XY[1] < XY[0]) return {1, 0};
        return {0};
    }
    vector<int> I(N);
    if (sorted) {
        for(int i = 0;i < N;i++) I[i] = i;
    } 
    else {
        iota(I.begin(),I.end(),0);
        sort(I.begin(),I.end(),[&](int i,int j) {return XY[i] < XY[j];});
    }
    if constexpr (allow_180) { for(int i = 0;i < N - 1;i++) assert(XY[i] != XY[i + 1]); }

    auto check = [&](int i, int j, int k) -> bool {
        T d = cross(XY[j] - XY[i],XY[k] - XY[i]);
        if constexpr (allow_180) return d >= 0;
        return d > T(0);
    };
    auto calc = [&]() {
        vector<int> P;
        for (auto&& k: I) {
        while (P.size() > 1) {
            auto i = P[P.size() - 2];
            auto j = P[P.size() - 1];
            if (check(i, j, k)) break;
            P.pop_back();
        }
            P.emplace_back(k);
        }
        return P;
    };

    vector<int> P;
    if (mode == "full" || mode == "lower") {
        vector<int> Q = calc();
        P.insert(P.end(),Q.begin(),Q.end());
    }
    if (mode == "full" || mode == "upper") {
        if (!P.empty()) P.pop_back();
        reverse(I.begin(),I.end());
        vector<int> Q = calc();
        P.insert(P.end(),Q.begin(),Q.end());
    }
    if (mode == "upper") reverse(P.begin(),P.end());
    while (P.size() >= 2 && XY[P[0]] == XY[P.back()]) P.pop_back();
    return P;
}
enum {
  OUT, ON, IN
};
int contains(const Polygon &Q, const Point &p) {
    bool in = false;
    for(int i = 0; i < Q.size(); i++) {
        Point a = Q[i] - p, b = Q[(i + 1) % Q.size()] - p;
        if(a.imag() > b.imag()) swap(a, b);
        if(a.imag() <= 0 && EPS < b.imag() && cross(a, b) < -EPS) in = !in;
        if(equals(cross(a, b),0) && dot(a, b) <= 0) return ON;
    }
    return in ? IN : OUT;
}
int convex_contains(const Polygon &Q, const Point &p) {
    if(Q.empty()) return OUT;
    if(Q.size() == 1) {
        return (equals(Q[0].real(),p.real()) && equals(Q[0].imag(),p.imag())) ? ON : OUT;
    }
    if(Q.size() == 2) {
        Segment s(Q[0],Q[1]);
        if(intersect(s,p)) return ON;
        else return OUT;
    }
    int N = (int) Q.size();
    Point g = (Q[0] + Q[N / 3] + Q[N * 2 / 3]) / (long double)3.0;
    if(g == p) return IN;
    Point gp = p - g;
    int l = 0, r = N;
    while(r - l > 1) {
        int mid = (l + r) / 2;
        Point gl = Q[l] - g;
        Point gm = Q[mid] - g;
        if(cross(gl, gm) > 0) {
            if(cross(gl, gp) >= 0 && cross(gm, gp) <= 0) r = mid;
            else l = mid;
        } 
        else {
            if(cross(gl, gp) <= 0 && cross(gm, gp) >= 0) l = mid;
            else r = mid;
        }
    }
    r %= N;
    Real v = cross(Q[l] - p, Q[r] - p);
    return equals(v, 0.0L) ? ON : v < 0.0L ? OUT : IN;
}
// deduplication of line segments
void merge_segments(vector<Segment> &segs) {
    auto merge_if_able = [](Segment &s1, const Segment &s2) {
        if (abs(cross(s1.b - s1.a, s2.b - s2.a)) > EPS) return false;
        if (ccw(s1.a, s2.a, s1.b) == 1 || ccw(s1.a, s2.a, s1.b) == -1) return false;
        if (ccw(s1.a, s1.b, s2.a) == -2 || ccw(s2.a, s2.b, s1.a) == -2)
        return false;
        s1 = Segment(min(s1.a, s2.a), max(s1.b, s2.b));
        return true;
    };
    for (int i = 0; i < segs.size(); i++) {
        if (segs[i].b < segs[i].a) swap(segs[i].a, segs[i].b);
    }
    for (int i = 0; i < segs.size(); i++) {
        for (int j = i + 1; j < segs.size(); j++) {
            if (merge_if_able(segs[i], segs[j])) {
                segs[j--] = segs.back(), segs.pop_back();
            }
        }
    }
}
// construct a graph with the vertex of the intersection of any two line
// segments
vector<vector<int>> segment_arrangement(vector<Segment> &segs,
                                         vector<Point> &ps) {
    vector<vector<int>> g;
    int N = (int)segs.size();
    for (int i = 0; i < N; i++) {
        ps.emplace_back(segs[i].a);
        ps.emplace_back(segs[i].b);
        for (int j = i + 1; j < N; j++) {
            const Point p1 = segs[i].b - segs[i].a;
            const Point p2 = segs[j].b - segs[j].a;
            if (cross(p1, p2) == 0) continue;
            if (intersect(segs[i], segs[j])) {
                ps.emplace_back(crosspoint(segs[i], segs[j]));
            }
        }
    }
    sort(begin(ps), end(ps));
    ps.erase(unique(begin(ps), end(ps)), end(ps));
    int M = (int)ps.size();
    g.resize(M);
    for (int i = 0; i < N; i++) {
        vector<int> vec;
        for (int j = 0; j < M; j++) {
            if (intersect(segs[i], ps[j])) {
                vec.emplace_back(j);
            }
        }
        for (int j = 1; j < vec.size(); j++) {
            g[vec[j - 1]].push_back(vec[j]);
            g[vec[j]].push_back(vec[j - 1]);
        }
    }
    return (g);
}
// cut with a straight line l and return a convex polygon on the left
Polygon convex_cut(const Polygon &U, Line l) {
    Polygon ret;
    for (int i = 0; i < U.size(); i++) {
      const Point &now = U[i];
      const Point &nxt = U[(i + 1) % U.size()];
      auto cf = cross(l.a - now, l.b - now);
      auto cs = cross(l.a - nxt, l.b - nxt);
      if (sign(cf) >= 0) {
        ret.emplace_back(now);
      }
      if (sign(cf) * sign(cs) < 0) {
        ret.emplace_back(crosspoint(Line(now, nxt), l));
      }
    }
    return ret;
}
long double area(const Polygon &p) {
    Real A = 0;
    for(int i = 0;i < (int)p.size();++i) {
        A += cross(p[i],p[(i+1) % p.size()]);
    }
    return A * .5;
}
long double area(const Polygon &p, const Circle &c) {
    if (p.size() < 3) return 0.0;
    auto cross_area =
        [&](auto &self,const Circle &c, const Point &a, const Point &b) {
            Point va = c.p - a, vb = c.p - b;
            long double f = cross(va, vb);
            long double ret = 0.0;
            if (equals(f, 0.0)) return ret;
            if (max(abs(va), abs(vb)) < c.r + EPS) return f;
            if (distance(Segment(a, b), c.p) > c.r - EPS) {
                Point conjva = va.conj();
                Point mulva = {vb.x * conjva.x - vb.y * conjva.y,vb.x * conjva.y + vb.y * conjva.x};
                return c.r * c.r * arg(mulva);
            }
            auto u = crosspoint(c, Segment(a, b));
            vector<Point> tot{a, u.first, u.second, b};
            for (int i = 0; i + 1 < tot.size(); i++) {
                ret += self(self, c, tot[i], tot[i + 1]);
            }
            return ret;
        };
    Real A = 0;
    for (int i = 0; i < p.size(); i++) {
        A += cross_area(cross_area, c, p[i], p[(i + 1) % p.size()]);
    }
    return A * 0.5;
}
template <typename T>
pair<int,int> furthest_pair(vector<PointBase<T>> p) {
    T best = -1;
    pair<int,int> ANS = {-1, -1};
    auto upd = [&](int i, int j) -> void {
        PointBase<T> p1 = p[i] - p[j];
        long long d = dot(p1,p1);
        if (best < d) {
            best = d;
            ANS = {i, j};
        }
    };
    upd(0, 1);
    auto I = convex_full(p);
    int n = I.size();
    if (n == 1) return ANS;
    if (n == 2) { return {I[0], I[1]}; }
    for(int i = 0;i < n;i++) I.emplace_back(I[i]);

    vector<PointBase<T>> C(I.size());
    for(int i = 0;i < I.size();i++) {
        C[i] = p[I[i]];
    }
    int j = 1;
    for(int i = 0;i < n;i++) {
        j = max(j,i);
        while (j < 2 * n && cross(C[i + 1] - C[i],C[j+1] - C[j]) > 0) ++j;
        upd(I[i], I[j]);
    }
    return ANS;
}
long double closest_pair(Points ps) {
    if (ps.size() <= 1) throw(0);
    sort(begin(ps), end(ps));
    auto compare_y = [&](const Point &a, const Point &b) {
        return imag(a) < imag(b);
    };
    vector<Point> beet(ps.size());
    const long double INF = 1e18;
    auto rec = [&](auto &self,int left, int right) {
        if (right - left <= 1) return INF;
        int mid = (left + right) >> 1;
        long double x = real(ps[mid]);
        auto ret = min(self(self, left, mid), self(self, mid, right));
        inplace_merge(begin(ps) + left, begin(ps) + mid, begin(ps) + right,
                    compare_y);
        int ptr = 0;
        for (int i = left; i < right; i++) {
            if (abs(real(ps[i]) - x) >= ret) continue;
            for (int j = 0; j < ptr; j++) {
                auto luz = ps[i] - beet[ptr - j - 1];
                if (imag(luz) >= ret) break;
                ret = min(ret, abs(luz));
            }
            beet[ptr++] = ps[i];
        }
        return ret;
    };
    return rec(rec, 0, (int)ps.size());
}
#line 100 "main.cpp"
int main() {
    INT(n);
    vector<PointBase<ll>> xy(n);
    rep(i,n) cin >> xy[i];
    auto ret = convex_full(xy);
    if(ret.size() == n) Yes();
    else No();
}
0