14609 구분구적법(Large)

14609 구분구적법(Large) https://www.acmicpc.net/problem/14609

$\int_{a}^{b}f(x)dx \approx \sum_{k=0}^{n-1}f(a+k \Delta x + \epsilon)\Delta x$
$\Delta x= (b-a)/n$
$0 \leq \epsilon \leq \Delta x$
$f(x)$, $a$,$b$, $n$이 주어질 때 근삿값이 적분값 $10^{-4}$이하의 오차를 만족하는 $\epsilon$을 구하는 문제다.

느낌적인 느낌으로 푼 문제다.
$\epsilon$이 어느 순간에 수렴하여 근삿값과 적분값이 일치할 때가 생길것 같았다.

삼분검색으로 해결했다.
이분탐색으로도 해결 가능하다.
근삿값이 적분값과 일치하지 않는$\epsilon$은 생기지 않는다.
즉, 위의 수식에 나온 범위내에서 만족하는 $\epsilon$은 항상 존재한다.

#include <cstdio> #include <cmath> using namespace std; int N, M, a, b; double s[11]; double x; double sum = 0.0; double isPossible(double mid) {     double ret = 0.0;     for (int m = 0;m < M;m++) {         double tmp = 0.0;         for (int n = N;n >= 0;n--) {             tmp += s[n] * (pow(a + m*x + mid, n));         }         tmp *= x;         ret += tmp;     }     return fabs(sum - ret); } int main() {     scanf("%d", &N);     for (int n = N;n >= 0;n--) scanf("%lf", &s[n]);     scanf("%d%d%d", &a, &b, &M);       for (int n = N;n >= 0;n--) sum += s[n] * (pow(b, n + 1) - pow(a, n + 1)) / (double)(n + 1);       int cnt = 0;     bool flag = false;     x = (b - a) / (double)M;     double l = 0.0, r = x;     while (1) {         double ll = (2 * l + r) / 3., rr = (l + 2 * r) / 3.;         double g1 = isPossible(ll), g2 = isPossible(rr);         if (g1 < g2) r = rr;         else l = ll;         if (++cnt == 10000) {             if (fabs(g1 - g2) <= 1e-4) flag = true;             break;         }     }     if (flag) printf("%lf\n", l);     else printf("-1\n");     return 0; } Colored by Color Scripter

cs