Submission #430201

#	Time	Username	Problem	Language	Result	Execution time	Memory
430201		palilo	공룡 발자국 (KOI18_footprint)	C++17	100 / 100	91 ms	460 KiB

footprint

#include <bits/stdc++.h>
using namespace std;

/* basics */
namespace geo {
#define EPS 1e-8
template <typename T, enable_if_t<is_integral<T>::value, bool> = true>
int sign(T x) { return (x > 0) - (x < 0); }
template <typename T, enable_if_t<is_floating_point<T>::value, bool> = true>
int sign(T x) { return (x > EPS) - (x < -EPS); }
}; // namespace geo

/* point2D */
namespace geo {
template <typename T>
struct point2D {
    T x, y;
    point2D() = default;
    point2D(T _x, T _y) : x(_x), y(_y) {}
    template <typename U>
    explicit point2D(const point2D<U>& p) : x(p.x), y(p.y) {}

    using P = point2D;

    bool operator<(const P& p) const { return tie(x, y) < tie(p.x, p.y); }
    bool operator==(const P& p) const { return tie(x, y) == tie(p.x, p.y); }
    bool operator!=(const P& p) const { return tie(x, y) != tie(p.x, p.y); }

    friend P operator+(const P& a, const P& b) { return P(a.x + b.x, a.y + b.y); }
    friend P operator-(const P& a, const P& b) { return P(a.x - b.x, a.y - b.y); }
    friend P operator*(const P& a, const T& scalar) { return P(a.x * scalar, a.y * scalar); }
    friend P operator*(const T& scalar, const P& a) { return P(scalar * a.x, scalar * a.y); }
    friend P operator/(const P& a, const T& scalar) { return P(a.x / scalar, a.y / scalar); }

    friend ostream& operator<<(ostream& o, const P& p) { return o << '(' << p.x << ", " << p.y << ')'; }
    friend istream& operator>>(istream& i, P& p) { return i >> p.x >> p.y; }

    T dot(const P& p) const { return x * p.x + y * p.y; }
    T cross(const P& p) const { return x * p.y - y * p.x; }
    T cross(const P& a, const P& b) const { return (a - *this).cross(b - *this); }

    T dist2() const { return x * x + y * y; }
    double dist() const { return sqrt(dist2()); }

    P perp_cw() const { return P(y, -x); }
    P perp_ccw() const { return P(-y, x); }

    P unit() const { return *this / dist(); }
    P normal() const { return perp_ccw().unit(); }

    P unit_int() const { return x || y ? *this / gcd(x, y) : *this; }
    P normal_int() const { return perp_ccw().unit_int(); }

    bool same_dir(const P& p) const { return cross(p) == 0 && dot(p) > 0; }
    int side_of(const P& s, const P& e) const {
        if constexpr (is_integral_v<T>) {
            return sign(s.cross(e, *this));
        } else {
            auto res = (e - s).cross(*this - s);
            double l = (e - s).dist() * EPS;
            return (res > l) - (res < -l);
        }
    }

    double angle() const { return atan2(y, x); }
    P rotate(double radian) const {
        return P(x * cos(radian) - y * sin(radian), x * sin(radian) + y * cos(radian));
    }
};
}; // namespace geo

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
#ifdef palilo
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif

    using point = geo::point2D<int64_t>;

    int n;
    cin >> n;

    vector<point> a(n);
    for (auto& p : a) cin >> p;

    swap(a.back(), *min_element(a.begin(), a.end(), [&](const auto& lhs, const auto& rhs) {
        return lhs.y < rhs.y;
    }));
    sort(a.begin(), a.end() - 1, [&](const auto& lhs, const auto& rhs) {
        return a.back().cross(lhs, rhs) < 0;
    });

    // {#, prev id}
    vector gol(n, -1), garak(n, 1);
    vector gol_prev(n, n - 1), garak_prev(n, n - 1);

    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (i != n - 1 && a.back().cross(a[j], a[i]) == 0) break;
            if (a[i].side_of(a[garak_prev[j]], a[j]) == -1) {
                if (gol[i] < garak[j] + 1 || (gol[i] == garak[j] + 1 && a[j].side_of(a[gol_prev[i]], a[i]) == 1))
                    gol[i] = garak[j] + 1, gol_prev[i] = j;
            }
            if (a[i].side_of(a[gol_prev[j]], a[j]) == 1) {
                if (garak[i] < gol[j] + 1 || (garak[i] == gol[j] + 1 && a[j].side_of(a[garak_prev[i]], a[i]) == -1))
                    garak[i] = gol[j] + 1, garak_prev[i] = j;
            }
        }
    }

    if (gol.back() < 4) return cout << 0, 0;

    vector<int> ans;
    ans.reserve(gol.back());

    for (int flag = 1, i = n - 1, cnt = gol.back(); cnt--; flag ^= 1) {
        ans.emplace_back(i);
        i = (flag ? gol_prev : garak_prev)[i];
    }

    cout << ans.size() << '\n';
    for (const auto& id : ans)
        cout << a[id].x << ' ' << a[id].y << '\n';
}

• Subtask 1: 14 / 14
• Subtask 2: 12 / 12
• Subtask 3: 29 / 29
• Subtask 4: 45 / 45