Submission #681432

#	Time	Username	Problem	Language	Result	Execution time	Memory
681432		Kamisama	먼 별 (KOI16_dist)	C++14	2 / 100	267 ms	2404 KiB

dist

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
 
template <class T>
void read(T &x)
{
    x = 0;
    register int c;
    while ((c = getchar()) && (c > '9' || c < '0'))
        ;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
}
 
constexpr bool typetest = 0;
constexpr int N = 3e4 + 5;
constexpr ll Inf = 1e17;
struct Point
{
    ll x, y;
    Point(const ll &x = 0, const ll &y = 0) : x(x), y(y) {}
    Point operator-(const Point &a) const
    {
        return Point(x - a.x, y - a.y);
    }
    Point operator*(const ll &v) const
    {
        return Point(x * v, y * v);
    }
    ll operator*(const Point &a) const
    {
        return x * a.y - y * a.x;
    }
    ll len() const
    {
        return x * x + y * y;
    }
    bool operator<(const Point &a) const
    {
        return x < a.x || (x == a.x && y < a.y);
    }
} a[N], d[N], b[N];
int n, t;
 
void Read()
{
    cin >> n >> t;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i].x >> a[i].y >> d[i].x >> d[i].y;
    }
}
 
ll f(ll t)
{
    // cout << t << ":\n";
    for (int i = 1; i <= n; ++i)
    {
        b[i] = a[i] - (d[i] * (-t));
    }
 
    sort(b + 1, b + n + 1);
    sort(b + 2, b + n + 1, [&](const Point &u, const Point &v)
         { Point uu = u - b[1],
                 vv = v - b[1];
            return uu * vv > 0 || (uu * vv == 0 && uu.len() < vv.len()); });
 
    int m = 2;
 
    for (int i = 3; i <= n; ++i)
    {
        while (m > 1 && (b[i] - b[m]) * (b[m] - b[m - 1]) >= 0)
            --m;
 
        b[++m] = b[i];
    }
 
    ll ans = 0;
 
    for (int i = 1, j = 1; i <= m; ++i)
    {
        while (j < m && (b[i] - b[j]).len() <= (b[i] - b[j + 1]).len()){
            ans = max(ans, (b[i] - b[j]).len());
            ++j;
        }
        ans = max(ans, (b[i] - b[j]).len());
    }
 
    return ans;
}
 
void Solve()
{
    if (t <= 20)
    {
        int l = 0;
        for (int i = 1; i <= t; ++i)
            if (f(i) < f(l))
                l = i;
        cout << l << "\n"
             << f(l);
    }
    else
    {
        int l = 0, m, h = t - 1;
        while (l <= h)
        {
            m = (l + h) / 2;
            if (f(m) > f(m + 1))
                l = m + 1;
            else
                h = m - 1;
        }
 
        cout << l << "\n"
             << f(l);
    }
}
 
int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    if (fopen("tests.inp", "r"))
    {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
 
    int t(1);
    if (typetest)
        cin >> t;
 
    for (int _ = 1; _ <= t; ++_)
    {
        // cout << "Case #" << _ << endl;
        Read();
        Solve();
    }
    // cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}

Compilation message (stderr)

dist.cpp: In function 'int32_t main()':
dist.cpp:132:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
dist.cpp:133:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 0 / 40
• Subtask 3: 0 / 39
• Subtask 4: 0 / 19