#include <stdio.h>
#include <stdlib.h>
struct im{
double r;
double i;
}
struct fereastra {
int i, j;
};
im arr[1000];
int n,m;
double l2(im x){// lungimea la patrat
return x.r * x.r + x.i * x.i;
}
fereastra algoritm(){
double s=0;
for(int i = 0; i<m; i++){//elem 0..m-1
s+=l2(arr[i]);
}
double maxs = s;
fereastra ret;
ret.i = 0;
ret.j = m-1;
for(int i = 0; i<n-1; i++){
s -= l2(arr[i]);
s+= l2(arr[(i+m%n)%n]);
if(s > maxs){
maxs = s;
ret.i = i+1;
ret.j = (i+m%n)%n;
}
}
return ret;
}
int main(){
scanf("%d %d", &n, &m);
for(int i = 0; i< n; i++){
scanf("%d %d", &(arr[i].r), &(arr[i].i));
}
fereastra rezultat = algoritm();
printf("Indice inceput fereastra: %d\nIndice sfarsit fereastra: %d\n", rezultat.i, rezultat.j);
}
Pentru un vector z:
[tex]z_0 z_1 \cdots z_{n-1}[/tex]
Putem lua de la inceput elementele 0... m-1, initializam suma initiala si suma maxima cu suma lor si apoi, mutam punctul de inceput al ferestrei un element mai la dreapta, devine suma
[tex]w_1+w_2+\cdots + w_m[/tex]
La urmatoarea iteratie:
[tex]w_2 + w_3+\cdots + w_{m+1}[/tex]
Putem trece de la suma unei ferestre la urmatoarea daca scadem primul element din fereastra iteratiei precedente si il adaugam pe cel imediat la dreapta ferestrei, verificand la fiecare iteratie daca am gasit o fereastra cu suma mai mare.
