verify/aoj-ITP1_10_D-nth_root.test.cpp

View this file on GitHub
Last update: 2025-07-03 00:41:25+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/10/ITP1_10_D

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/10/ITP1_10_D"
#define ERROR 1e-5

#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>

#include "../algorithm/Math/Algebra/nth_root.hpp"
#include "../algorithm/Math/Algebra/power.hpp"

int main() {
    int n;
    std::cin >> n;

    std::vector<int> x(n), y(n);
    for(auto &elem : x) std::cin >> elem;
    for(auto &elem : y) std::cin >> elem;

    auto f = [&](int p) -> double {
        double tmp = 0.0;
        for(int i = 0; i < n; ++i) tmp += algorithm::pow(std::abs(x[i] - y[i]), p);
        return algorithm::nth_root(tmp, p, 1e-10);
    };
    auto g = [&]() -> int {
        int res = 0;
        for(int i = 0; i < n; ++i) res = std::max(res, std::abs(x[i] - y[i]));
        return res;
    };

    for(int p = 1; p <= 3; ++p) printf("%.8lf\n", f(p));
    std::cout << g() << std::endl;
}

#line 1 "verify/aoj-ITP1_10_D-nth_root.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/10/ITP1_10_D"
#define ERROR 1e-5

#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>

#line 1 "algorithm/Math/Algebra/nth_root.hpp"



#include <cassert>
#line 6 "algorithm/Math/Algebra/nth_root.hpp"

#line 1 "algorithm/Math/Algebra/power.hpp"



#line 5 "algorithm/Math/Algebra/power.hpp"

namespace algorithm {

// 繰り返し二乗法．O(logK).
template <typename Type>
constexpr Type pow(Type n, long long k) {
    assert(k >= 0);
    Type res = 1;
    while(k > 0) {
        if(k & 1LL) res *= n;
        n *= n;
        k >>= 1;
    }
    return res;
}

}  // namespace algorithm


#line 8 "algorithm/Math/Algebra/nth_root.hpp"

namespace algorithm {

// 累乗根（ニュートン法）．xのn乗根を求める．
constexpr double nth_root(double x, long long n, double eps = 1e-10) {
    assert(x >= 0.0);
    assert(n >= 1);
    double res = 1.0;
    while(true) {
        double tmp = (x / pow(res, n - 1) + (n - 1) * res) / n;
        if(std::abs(tmp - res) < eps) break;
        res = tmp;
    }
    return res;
}

}  // namespace algorithm


#line 11 "verify/aoj-ITP1_10_D-nth_root.test.cpp"

int main() {
    int n;
    std::cin >> n;

    std::vector<int> x(n), y(n);
    for(auto &elem : x) std::cin >> elem;
    for(auto &elem : y) std::cin >> elem;

    auto f = [&](int p) -> double {
        double tmp = 0.0;
        for(int i = 0; i < n; ++i) tmp += algorithm::pow(std::abs(x[i] - y[i]), p);
        return algorithm::nth_root(tmp, p, 1e-10);
    };
    auto g = [&]() -> int {
        int res = 0;
        for(int i = 0; i < n; ++i) res = std::max(res, std::abs(x[i] - y[i]));
        return res;
    };

    for(int p = 1; p <= 3; ++p) printf("%.8lf\n", f(p));
    std::cout << g() << std::endl;
}