結果
問題 | No.3154 convex polygon judge |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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(); }