#include<stdio.h>
#include<math.h>
#include<string.h>

typedef struct _stanica{
  char ime[61];
  double x,y;
  int br;
  struct _stanica *next;
}stanica;

double trosak(stanica* pom1, stanica* pom2){
  double rje;
  rje=pom1->br/sqrt((((pom2->x)-(pom1->x))*((pom2->x)-(pom1->x)))+(((pom2->y)-(pom1->y))*((pom2->y)-(pom1->y))));
  return rje;
}

stanica* dodaj_stanicu(stanica* first, stanica* nova){
  if(first==NULL) //ekstremni slucajevi
    { nova->next=NULL;
      return nova;
    }
  if((first->next)==NULL){
    first->next=nova;
    nova->next=NULL;
    return first;
  }
  double suma, sumamin=trosak(first, nova)+trosak(nova, first->next);
  stanica* pom;
  stanica* pom2;
  for(pom=first; pom->next!=NULL; pom=pom->next){
    suma=trosak(pom, nova)+trosak(nova, pom->next);
    if(suma<sumamin){
      sumamin=suma;
      pom2=pom; // da znamo na koje mjesto ga treba ubacit
    }
  }
    nova->next=(pom2->next);
    pom2->next=nova;
  return first;
}

int izvan(stanica* pom2, stanica* pom1, double r){
  double udaljenost=sqrt((((pom2->x)-(pom1->x))*((pom2->x)-(pom1->x)))+(((pom2->y)-(pom1->y))*((pom2->y)-(pom1->y))));
  if(udaljenost>r)return 1;
  return 0;
}

stanica* izdvoji(stanica** first, char *naziv, double rad){
  stanica* pom;
  stanica* nova;
  stanica* pom2=NULL;
  for(pom=*first; pom!=NULL; pom=pom->next)
    if(!strcmp(naziv, pom->ime)){
        pom2=pom;
        break;
    }
  if(pom2==NULL)return NULL;
  for(pom=*first; pom->next!=NULL; pom=pom->next){
      if(izvan(pom->next, pom2, rad)){
          stanica* temp=pom->next;
          pom->next=temp->next;
          nova=dodaj_stanicu(nova, pom->next);
          free(temp);
      }
  }
 if(izvan(pom2, (*first), rad)==1){ //posebna provjera prvog
  stanica* temp=(*first);
  nova=dodaj_stanicu(nova, (*first));
  free(*first);
  return temp->next;
 }
 return nova;
}

void ispisi(stanica *first) {
  while(first != NULL) {
    printf("%s x=%lf y=%lf broj=%d\n",
           first->ime, first->x, first->y, first->br);
    first = first->next;
  }
}

int main(void) {
  stanica *izbaceni;
  stanica s1 = {"prvi", 0, 0, 10, NULL};
  stanica s2 = {"drugi", 1, 1, 5, NULL};
  stanica s3 = {"treci", -1, 1, 6, NULL};
  stanica s4 = {"cetvrti", 1, -1, 7, NULL};
  stanica s5 = {"peti", -1, -1, 12, NULL};
  stanica s6 = {"sesti", 4, 3, 13, NULL};
  stanica s7 = {"sedmi", 3, 2, 14, NULL};

  stanica *lista = NULL;
  lista = dodaj_stanicu(lista, &s1);
  lista = dodaj_stanicu(lista, &s2);
  lista = dodaj_stanicu(lista, &s3);
  lista = dodaj_stanicu(lista, &s4);
  lista = dodaj_stanicu(lista, &s5);
  lista = dodaj_stanicu(lista, &s6);
  lista = dodaj_stanicu(lista, &s7);
  printf("originalna lista:\n");
  ispisi(lista);

  izbaceni = izdvoji(&lista, "sedmi", 3.0);
  printf("izbacene stanice:\n");
  ispisi(izbaceni);

  printf("preostale stanice:\n");
  ispisi(lista);

  return 0;
}