#!/usr/bin/env perl
use strict;
use warnings;
use utf8;
use Math::BigRat;

# usage
# perl Lagrange_form.pl 1,2 2,3 3,5 2.5

sub Lagrange {
    my ($sets_ref, $x) = @_;
    my @Z = @$sets_ref;
    my $forms;

    for my $i (0..$#Z) {
        my $form = 1;
        for my $j (0..$#Z) {
            next if $i == $j;
            $form *= ($x - $Z[$j]->[0]) / ($Z[$i]->[0] - $Z[$j]->[0]);
        }
        $forms += $Z[$i]->[1] * $form;
    }

    return sprintf "%f", $forms;
}

# 多項式の係数を計算する
sub LagrangeCoefficients {
    my ($sets_ref) = @_;
    my @Z = @$sets_ref;
    my @coefficients = (0) x @Z;  # 多項式の係数を初期化

    for my $i (0..$#Z) {
        my @term = (1);  # 現在の項を保持する配列（多項式の形式）
        for my $j (0..$#Z) {
            next if $i == $j;
            my @new_term = (0);
            for my $k (0..$#term) {
                $new_term[$k] += -$Z[$j]->[0] * $term[$k];
                $new_term[$k + 1] = $term[$k];
            }
            @term = map { $_ / ($Z[$i]->[0] - $Z[$j]->[0]) } @new_term;
        }
        for my $k (0..$#term) {
            $coefficients[$k] += $term[$k] * $Z[$i]->[1];
        }
    }

    return @coefficients;
}

# コマンドライン引数の処理
my @args = @ARGV;
die "Usage: perl your_script.pl x1,y1 x2,y2 ... x_n,y_n x_value\n" unless @args > 1;

# 最後の引数が求めたいx座標
my $x_value = pop @args;

# 入力座標を有理数に変換
my @points = map { [ map { Math::BigRat->new($_) } split /,/ ] } @args;

# ラグランジュ補間の計算と結果出力
print "Interpolated value at x=$x_value: " . Lagrange(\@points, $x_value) . "\n";

# 多項式の係数を出力
my @coefficients = LagrangeCoefficients(\@points);
print "Polynomial coefficients (from highest to lowest degree):\n";
print join(", ", @coefficients) . "\n";