Submission #1248401

#TimeUsernameProblemLanguageResultExecution timeMemory
1248401repeat21Mobile (BOI12_mobile)C++20
50 / 100
1096 ms81016 KiB
#include <algorithm> #include <array> #include <cassert> #include <climits> #include <cmath> #include <cstdint> #include <cstdlib> #include <iomanip> #include <iostream> #include <map> #include <numeric> #include <queue> #include <set> #include <string> #include <unordered_map> #include <vector> void setIO(std::string name = "", int precision = -1) { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); if (!name.empty()) { freopen((name + ".in").c_str(), "r", stdin); freopen((name + ".out").c_str(), "w", stdout); } if (precision >= 0) { std::cout << std::fixed << std::setprecision(precision); } } using namespace std; template <typename T> T inverse(T a, T m) { T u = 0, v = 1; while (a != 0) { T t = m / a; m -= t * a; swap(a, m); u -= t * v; swap(u, v); } assert(m == 1); return u; } template <typename T> class Modular { public: using Type = typename decay<decltype(T::value)>::type; constexpr Modular() : value() {} template <typename U> Modular(const U& x) { value = normalize(x); } template <typename U> static Type normalize(const U& x) { Type v; if (-mod() <= x && x < mod()) v = static_cast<Type>(x); else v = static_cast<Type>(x % mod()); if (v < 0) v += mod(); return v; } const Type& operator()() const { return value; } template <typename U> explicit operator U() const { return static_cast<U>(value); } constexpr static Type mod() { return T::value; } Modular& operator+=(const Modular& other) { value += other.value; value -= (value >= mod()) * mod(); return *this; } Modular& operator-=(const Modular& other) { value -= other.value; value += (value < 0) * mod(); return *this; } template <typename U> Modular& operator+=(const U& other) { return *this += Modular(other); } template <typename U> Modular& operator-=(const U& other) { return *this -= Modular(other); } Modular& operator++() { return *this += 1; } Modular& operator--() { return *this -= 1; } Modular operator++(int) { Modular result(*this); *this += 1; return result; } Modular operator--(int) { Modular result(*this); *this -= 1; return result; } Modular operator-() const { return Modular(-value); } template <typename U = T> typename enable_if<is_same<typename Modular<U>::Type, int>::value, Modular>::type& operator*=(const Modular& rhs) { value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value)); return *this; } template <typename U = T> typename enable_if<is_same<typename Modular<U>::Type, int64_t>::value, Modular>::type& operator*=(const Modular& rhs) { int64_t q = int64_t(static_cast<long double>(value) * rhs.value / mod()); value = normalize(value * rhs.value - q * mod()); return *this; } template <typename U = T> typename enable_if<!is_integral<typename Modular<U>::Type>::value, Modular>::type& operator*=(const Modular& rhs) { value = normalize(value * rhs.value); return *this; } Modular& operator/=(const Modular& other) { return *this *= Modular(inverse(other.value, mod())); } friend const Type& abs(const Modular& x) { return x.value; } template <typename U> friend bool operator==(const Modular<U>& lhs, const Modular<U>& rhs); template <typename U> friend bool operator<(const Modular<U>& lhs, const Modular<U>& rhs); template <typename V, typename U> friend V& operator>>(V& stream, Modular<U>& number); private: Type value; }; template <typename T> bool operator==(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value == rhs.value; } template <typename T, typename U> bool operator==(const Modular<T>& lhs, U rhs) { return lhs == Modular<T>(rhs); } template <typename T, typename U> bool operator==(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) == rhs; } template <typename T> bool operator!=(const Modular<T>& lhs, const Modular<T>& rhs) { return !(lhs == rhs); } template <typename T, typename U> bool operator!=(const Modular<T>& lhs, U rhs) { return !(lhs == rhs); } template <typename T, typename U> bool operator!=(U lhs, const Modular<T>& rhs) { return !(lhs == rhs); } template <typename T> bool operator<(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value < rhs.value; } template <typename T> Modular<T> operator+(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; } template <typename T, typename U> Modular<T> operator+(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) += rhs; } template <typename T, typename U> Modular<T> operator+(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; } template <typename T> Modular<T> operator-(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; } template <typename T, typename U> Modular<T> operator-(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) -= rhs; } template <typename T, typename U> Modular<T> operator-(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; } template <typename T> Modular<T> operator*(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; } template <typename T, typename U> Modular<T> operator*(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) *= rhs; } template <typename T, typename U> Modular<T> operator*(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; } template <typename T> Modular<T> operator/(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; } template <typename T, typename U> Modular<T> operator/(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) /= rhs; } template <typename T, typename U> Modular<T> operator/(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; } template <typename T, typename U> Modular<T> power(const Modular<T>& a, const U& b) { assert(b >= 0); Modular<T> x = a, res = 1; U p = b; while (p > 0) { if (p & 1) res *= x; x *= x; p >>= 1; } return res; } template <typename T> bool IsZero(const Modular<T>& number) { return number() == 0; } template <typename T> string to_string(const Modular<T>& number) { return to_string(number()); } // U == std::ostream? but done this way because of fastoutput template <typename U, typename T> U& operator<<(U& stream, const Modular<T>& number) { return stream << number(); } // U == std::istream? but done this way because of fastinput template <typename U, typename T> U& operator>>(U& stream, Modular<T>& number) { typename common_type<typename Modular<T>::Type, int64_t>::type x; stream >> x; number.value = Modular<T>::normalize(x); return stream; } // using ModType = int; // struct VarMod { static ModType value; }; // ModType VarMod::value; // ModType& md = VarMod::value; // using Mint = Modular<VarMod>; constexpr int md = 1'000'000'007; using Mint = Modular< std::integral_constant < decay< decltype(md) >::type, md >>; template <typename T> using MinHeap = std::priority_queue<T, std::vector<T>, std::greater<T>>; using ll = long long; using ld = long double; struct Seg { long long x; long long y; long long val; bool operator<(const Seg& seg) const { return x < seg.x; } bool operator>(const Seg& seg) const { return y > seg.y; } Seg(int x, int y, int val) : x(x), y(y), val(val) {} }; pair<ld, ld> get_seg(pair<ld, ld> p, ld rad) { ld dx = sqrtl(max(0.0L, rad * rad - p.second * p.second)); return {p.first - dx, p.first + dx}; } int main() { setIO("", 6); int n; ld l; cin >> n >> l; vector<pair<ld, ld>> points; for (int i = 0; i < n; ++i) { ld x, y; cin >> x >> y; points.emplace_back(x, y); } auto check = [&](ld cur_rad) { vector<pair<ld, ld>> segments = {{0, 0}}; transform(points.begin(), points.end(), back_inserter(segments), [cur_rad](pair<ld, ld>& p) { return get_seg(p, cur_rad); }); segments.emplace_back(l, l); ld mx = 0; for (auto seg : segments) { if (mx < seg.first) { continue; } mx = max(mx, seg.second); } return mx >= l; }; ld low = 0, high = 1e10; while ((high - low) > 1e-5) { ld mid = (low + high) / 2; if (check(mid)) { high = mid; } else { low = mid; } } cout << high; }

Compilation message (stderr)

mobile.cpp: In function 'void setIO(std::string, int)':
mobile.cpp:24:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |     freopen((name + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mobile.cpp:25:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     freopen((name + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...