oj.uz

답안 #646761

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
646761 2022-09-30T15:12:03 Z pls33 Mobile (BOI12_mobile) C++17
0 / 100
 231 ms 42612 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#pragma region dalykai
using p32 = pair<int, int>;
using p32u = pair<uint32_t, uint32_t>;
using p64 = pair<int64_t, int64_t>;
using p64u = pair<uint64_t, uint64_t>;
using vi16 = vector<int16_t>;
using vi16u = vector<uint16_t>;
using vi32 = vector<int>;
using vi32u = vector<uint32_t>;
using vi64 = vector<int64_t>;
using vi64u = vector<uint64_t>;
using vp32 = vector<p32>;
using vp32u = vector<p32u>;
using vp64 = vector<p64>;
using vp64u = vector<p64u>;
using vvi32 = vector<vi32>;
using vvi32u = vector<vi32u>;
using vvi64 = vector<vi64>;
using vvi64u = vector<vi64u>;
using vvp32 = vector<vp32>;
using vvp32u = vector<vp32u>;
using vvp64 = vector<vp64>;
using vvp64u = vector<vp64u>;

using pf32 = pair<float, float>;
using pf64 = pair<double, double>;
using pf80 = pair<long double, long double>;
using vf32 = vector<float>;
using vf64 = vector<double>;
using vf80 = vector<long double>;
using vpf32 = vector<pf32>;
using vpf64 = vector<pf64>;
using vpf80 = vector<pf80>;
using vvf32 = vector<vf32>;
using vvf64 = vector<vf64>;
using vvf80 = vector<vf80>;
using vvpf32 = vector<vpf32>;
using vvpf64 = vector<vpf64>;
using vvpf80 = vector<vpf80>;

template <typename key, typename val>
using ord_map = tree<key, val, less<key>, rb_tree_tag,
                     tree_order_statistics_node_update>;

template <typename key>
using ord_set = tree<key, null_type, less<key>, rb_tree_tag,
                     tree_order_statistics_node_update>;

const int BUF_SZ = 1 << 15;
inline namespace fast_in
{
    char buf[BUF_SZ];
    int pos;
    int len;

    char next_char(FILE *f)
    {
        if (pos == len)
        {
            pos = 0;
            len = (int)fread(buf, 1, BUF_SZ, f);

            if (!len)
            {
                return EOF;
            }
        }

        return buf[pos++];
    }

    int read_int(FILE *f)
    {
        int x;
        char ch;
        int sgn = 1;

        while (!isdigit(ch = next_char(f)))
        {
            if (ch == '-')
            {
                sgn *= -1;
            }
        }

        x = ch - '0';
        while (isdigit(ch = next_char(f)))
        {
            x = x * 10 + (ch - '0');
        }

        return x * sgn;
    }
}

/**
 * @brief gale programos flush_out kviest!!
 */
inline namespace fast_out
{
    char buf[BUF_SZ];
    int pos;

    void flush_out(FILE *f)
    {
        fwrite(buf, 1, pos, f);
        pos = 0;
    }

    void write_char(char c, FILE *f)
    {
        if (pos == BUF_SZ)
        {
            flush_out(f);
        }

        buf[pos++] = c;
    }

    void write_int(int x, FILE *f)
    {
        static char num_buf[100];

        if (x < 0)
        {
            write_char('-', f);
            x *= -1;
        }

        int len = 0;
        for (; x >= 10; x /= 10)
        {
            num_buf[len++] = (char)('0' + (x % 10));
        }

        write_char((char)('0' + x), f);
        while (len)
        {
            write_char(num_buf[--len], f);
        }
        write_char('\n', f);
    }
}
#pragma endregion

using fl_t = double;
const fl_t __eps = 1e-6;

// !!!!!!!!!!!!!!
#define __x real
// !!!!!!!!!!!!!!
#define __y imag
using point_t = complex<fl_t>;

fl_t dot(point_t a, point_t b)
{
    return (conj(a) * b).__x();
}

fl_t cross(point_t a, point_t b)
{
    return (conj(a) * b).__y();
}

struct cht_t
{
    deque<point_t> hull, normal;

    void add(fl_t k, fl_t b)
    {
        point_t nw = {k, b};
        while (!normal.empty() && dot(normal.back(), nw - hull.back()) < 0)
        {
            hull.pop_back();
            normal.pop_back();
        }
        if (!hull.empty())
        {
            normal.push_back(1i * (nw - hull.back()));
        }
        hull.push_back(nw);
    }

    fl_t get(fl_t x)
    {
        point_t query = {x, 1};
        auto it = lower_bound(normal.begin(), normal.end(), query, [](point_t a, point_t b)
                              { return cross(a, b) > 0; });

        point_t &line = hull[it - normal.begin()];
        return dot(query, line);
    }
};

void add(point_t p, cht_t &cht)
{
    fl_t k = -2 * p.__x();
    fl_t b = p.__x() * p.__x() + p.__y() * p.__y();

    // - nes reik minimumo mum
    cht.add(k, b);
}

fl_t query(fl_t x, cht_t &cht)
{
    return x * x + cht.get(x);
}

fl_t ternary_search(fl_t l, fl_t r, cht_t &cht)
{
    while (r - l > __eps)
    {
        fl_t m_l = l + (r - l) / 3;
        fl_t m_r = r - (r - l) / 3;

        if (query(m_l, cht) < query(m_r, cht))
        {
            l = m_l;
        }
        else
        {
            r = m_r;
        }
    }

    return query(l, cht);
}

int main()
{
#ifndef _AAAAAAAAA
    ios_base::sync_with_stdio(false);
    cin.tie(0);
#else
    freopen("mobile.in", "r", stdin);
#ifndef __linux__
    atexit([]()
           {
            freopen("con", "r", stdin);
            system("pause"); });
#endif
#endif

    int n, length;
    cin >> n >> length;

    cht_t cht;
    vp32 station(n);
    for (size_t i = 0; i < n; i++)
    {
        cin >> station[i].first >> station[i].second;
    }
    for (int i = n - 1; i >= 0; i--)
    {
        fl_t a = station[i].first;
        if (abs(station[i].first) < __eps)
        {
            a = __eps;
        }
        fl_t b = station[i].second;

        add({a, b}, cht);
    }

    fl_t res = sqrt(max({ternary_search(0, length, cht),
                         query(0, cht),
                         query(length, cht)}));

    cout << res << '\n';

    return 0;
}

Compilation message

mobile.cpp:8: warning: ignoring '#pragma region dalykai' [-Wunknown-pragmas]
    8 | #pragma region dalykai
      | 
mobile.cpp:151: warning: ignoring '#pragma endregion ' [-Wunknown-pragmas]
  151 | #pragma endregion
      | 
mobile.cpp: In function 'int main()':
mobile.cpp:256:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  256 |     for (size_t i = 0; i < n; i++)
      |                        ~~^~~

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 320 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 412 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 1932 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 1620 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 4596 KB Output is correct
2 Incorrect 33 ms 2120 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 21 ms 2620 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 26 ms 4540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 86 ms 22700 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 178 ms 6148 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 96 ms 26724 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 128 ms 6624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 103 ms 30572 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 148 ms 11508 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 127 ms 34620 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 185 ms 12308 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 148 ms 42612 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 231 ms 13272 KB Output isn't correct
2 Halted 0 ms 0 KB -