/*
 * bisection.cpp -- 二分法 (bisection method) で方程式 f(x)=0 を解く
 *   コンパイル: c++ bisection.cpp
 *   実行:       ./a.out
 *
 *   http://verifiedby.me/kv/simple/interval-simple-0.4.48.tar.gz に
 *   入っている interval.hpp を使います。
 */

#include <iostream>
#include <iomanip>
#include <cmath>
#include "interval.hpp"

using namespace std;

void print(interval x, interval fx, string s);
void print2(interval x, interval fx);

interval f(interval x)
{
  return cos(x) - x;
}

int main(void)
{
  int i, maxitr = 100;
  int fa_plus, fb_plus, fc_plus;
  double alpha, beta, eps;
  interval a, b, c, x;
  interval fa, fb, fc, fx;

  cout << " 探す区間の左端α, 右端β, 許容精度ε=";
  cin >> alpha >> beta >> eps;

  a = alpha; fa = f(a);
  if (in(0, fa)) {
    print(a, fa, ": 符号の判定が出来ない。\n");
    exit(0);
  }
  b = beta;  fb = f(b);
  if (in(0,fb)) {
    print(b, fb, ": 符号の判定が出来ない。\n");
    exit(0);
  }
  fa_plus = f(a) > 0;
  fb_plus = f(b) > 0;
  if ((fa_plus && fb_plus) || (!fa_plus && !fb_plus)) {
    print(a, fa, ","); print(b, fb, " 同符号なのであきらめます。\n");
    exit(0);
  }
  print(a, fa, ", "); print(b, fb, "\n");
  for (i = 0; i < maxitr; i++) {
    c = (a + b) / 2; fc = f(c); fc_plus = (fc > 0);
    if (in(0,fc)) {
      print(c, fc, ": 中点で符号の判定ができません。ここまでの結果を出力します。\n");
      break;
    }
    else if ((fa_plus && !fc_plus) || (!fa_plus && fc_plus)) {
      /* 左側 [a,c] に根がある */
      b = c; fb = fc; fb_plus = fc_plus;
      cout << "                         ";
      print(b, fb, "\n");
    }
    else if ((!fc_plus && fb_plus) || (fc_plus && !fb_plus)) {
      /* 右側 [c,b] にあるはず */
      a = c; fa = fc; fa_plus = fc_plus;
      print(a, fa, "\n");
    }
    else {
      cout << "ここに来ないはず。おかしい。" << endl;
      exit(1);
    }
    if ((b - a) <= eps) {
      cout << "区間の幅がeps=" << scientific << setprecision(2) << eps
	   << "より小さくなりました。" << endl;
      break;
    }
  }
  print2(a, fa); print2(b, fb);
  return 0;
}

// xの値, f(x) の正負, 文字列 s を表示する。
void print(interval x, interval fx, string s)
{
  cout << "f(" << fixed << setprecision(16) << mid(x) << ")";
  if (fx > 0)
    cout << ">0" << s;
  else if (fx < 0)
    cout << "<0" << s;
  else
    cout << "=?" << s;
}

// xの値, f(x)の値を表示して改行する。
void print2(interval x, interval fx)
{
  cout << "f(" << fixed << setprecision(16) << x << ")="
       << scientific << setprecision(2) << fx;
  if (fx > 0)
    cout << ">0" << endl;
  else if (fx < 0)
    cout << "<0" << endl;
  else
    cout << "=?" << endl;
}