結果
| 問題 |
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 |
ソースコード
#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();
}