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