Interpolation (200 pts)

Question:

NEWTON is an autonomous unmanned aerial vehicle (UAV). Where did the UAV refuel at t=180?

Path planning:

t x y

0; 35.645592; 50.951123;

20; 35.144068; 50.467725;

40; 34.729775; 48.204541;

60; 34.204433; 46.117139;

80; 33.602623; 44.908643;

100; 33.162285; 42.337842;

120; 33.712359; 40.140576;

140; 33.931410; 38.580518;

150; 33.894940; 37.745557;

170; 33.474422; 36.273389;

190; 35.32583531; 35.663648;

210; 33.130089; 35.19047214;

220; 32.409544; 35.141797;

230; 32.085525; 34.786115;

The flag is: [the bridge's name near the refule place]_[Latitude of the place with 5 digits after the decimal point]_[Longitude of the place with 5 digits after the decimal point].

Write-Up:

The question's name is Interpolation and the name of UAV is NEWTON, So you can solve it easily by NEWTON Interpolation Algorithm. There are many NEWTON algorithms in Internet, like this:

#include<stdio.h>
#include<conio.h>

void main()
{
    int x[10], y[10], p[10];
    int k,f,n,i,j=1,f1=1,f2=0;
    printf("\nEnter the number of observations:\n");
    scanf("%d", &n);

    printf("\nEnter the different values of x:\n");
    for (i=1;i<=n;i++)
        scanf("%d", &x[i]);

    printf("\nThe corresponding values of y are:\n");
    for (i=1;i<=n;i++)
        scanf("%d", &y[i]);

    f=y[1];
    printf("\nEnter the value of 'k' in f(k) you want to evaluate:\n");
    scanf("%d", &k);

    do
    {
        for (i=1;i<=n-1;i++)
        {
            p[i] = ((y[i+1]-y[i])/(x[i+j]-x[i]));
            y[i]=p[i];
        }
        f1=1;
        for(i=1;i<=j;i++)
            {
                f1*=(k-x[i]);
            }
        f2+=(y[1]*f1);
        n--;
        j++;
    }

    while(n!=1);
    f+=f2;
    printf("\nf(%d) = %d", k , f);
    getch();
}

See further information here.

Calculate two Newton interpolation, once for (t, x) and the other for (t, y), as below:

result for x: 
Degree, Coefficients
     0, 35.64559200
     1, -3.18915616
     2, 0.46511059
     3, -0.02813243
     4, 0.00094181
     5, -0.00001964
     6, 0.00000027
     7, -0.00000000
     8, 0.00000000
     9, -0.00000000
    10, 0.00000000
    11, -0.00000000
    12, 0.00000000


result for y:
Degree, Coefficients
     0, 50.95112300
     1, -1.72520149
     2, 0.24101994
     3, -0.01360238
     4, 0.00040968
     5, -0.00000750
     6, 0.00000009
     7, -0.00000000
     8, 0.00000000
     9, -0.00000000
    10, 0.00000000
    11, -0.00000000
    12, 0.00000000

So for t=180:

    x=Decimal Deg. Latitude= 34.06829331 
    y=Decimal Deg. Longitude=35.88253677

Use Google Map and find the bridge, there is a bridge near the mentioned x, y named Afqa Bridge.

The bridge in google map .

The flag is afqa_34.06829_35.88253.