daily pastebin goal
62%
SHARE
TWEET

Deda_mraz

a guest Jan 11th, 2019 71 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<math.h>
  4. #include<string.h>
  5.  
  6. struct tree{
  7.     int id,balance,broj_dece,deca[100];
  8.     float x,y;
  9.     struct tree *left,*right;
  10. };
  11.  
  12. #define novi(x) x=(struct tree*)malloc(sizeof(struct tree))
  13.  
  14. int dubina(struct tree *p)
  15. {
  16.     int dl=0,dr=0;
  17.     if(p)
  18.     {
  19.         if(p->left)dubina(p->left);
  20.         if(p->right)dubina(p->right);
  21.         if(dl>dr) return ++dl;
  22.         else return ++dr;
  23.     }
  24.     else return 0;
  25. }
  26.  
  27. void lrotation(struct tree **t)
  28. {
  29.     struct tree *poml,*pomr;
  30.     poml=*t;
  31.     pomr=poml->right;
  32.     poml->right=pomr->left;
  33.     pomr->left=poml;
  34.     *t=pomr;
  35.     poml->balance=dubina(poml->right)-dubina(poml->left);
  36.     pomr->balance=dubina(pomr->right)-dubina(pomr->left);
  37.    
  38. }
  39.  
  40. void rrotation(struct tree **t)
  41. {
  42.     struct tree *poml,*pomr;
  43.     pomr=*t;
  44.     poml=pomr->left;
  45.     pomr->left=poml->right;
  46.     poml->right=pomr;
  47.     *t=poml;
  48.     poml->balance=dubina(poml->right)-dubina(poml->left);
  49.     pomr->balance=dubina(pomr->right)-dubina(pomr->left);
  50. }
  51.  
  52. float rastojanje(float x,float y)
  53. {
  54.     float r;
  55.     r=sqrt(pow(x,2)+pow(y,2));
  56.     return r;
  57. }
  58.  
  59. int dodaj(struct tree **p,int id, int br_dece,int *deca,float x,float y)
  60. {
  61.     struct tree *t=*p;
  62.     int inc,res=0,i;
  63.     if(!t)
  64.     {
  65.         novi(t);
  66.         if(!t) printf("Greska\n");
  67.         t->id=id;
  68.         t->broj_dece=br_dece;
  69.         for(i=0;i<br_dece;i++)
  70.             t->deca[i]=deca[i];
  71.         t->x=x;
  72.         t->y=y;
  73.         t->balance=0;
  74.         t->left=t->right=0;
  75.         res=1;
  76.     }
  77.     else
  78.     {
  79.         if((rastojanje(x,y)) > (rastojanje(t->x,t->y))) inc=dodaj(&(t->right),id,br_dece,deca,x,y);
  80.         else inc=-dodaj(&(t->left),id,br_dece,deca,x,y);
  81.         t->balance+=inc;
  82.         if(inc!=0 && t->balance!=0){
  83.             if(t->balance<-1){
  84.                 if(t->left->balance<0)rrotation(&t);
  85.                 else { lrotation(&(t->left)); rrotation(&t);}
  86.             }
  87.             else if(t->balance>1){
  88.                 if(t->right->balance>0) lrotation(&t);
  89.                 else { rrotation(&(t->right)); lrotation(&t);}
  90.             }
  91.             else res=1;
  92.         }
  93.     }
  94.     *p=t;
  95.     return res;
  96. }
  97.  
  98. struct tree *form(int n)
  99. {
  100.     struct tree *root=NULL;
  101.     int id,broj_dece,*deca=(int*)malloc(sizeof(int)*100),i,j;
  102.     float x,y;
  103.     for(i=0;i<n;i++)
  104.     {
  105.         scanf(" %d %d",&id,&broj_dece);
  106.         for(j=0;j<broj_dece;j++)
  107.             scanf("%d",&deca[j]);
  108.         scanf("%f %f",&x,&y);
  109.         dodaj(&root,id,broj_dece,deca,x,y);
  110.     }
  111.     return root;
  112. }
  113.  
  114. void ispis(struct tree *p)
  115. {
  116.     int i;
  117.     if(p)
  118.     {
  119.         if(p->left)ispis(p->left);
  120.         printf("id_dm: %d\nbroj_dece: %d\n",p->id,p->broj_dece);
  121.         printf("Deca: ");
  122.         for(i=0;i<p->broj_dece;i++)
  123.             printf("%3d",p->deca[i]);
  124.         printf("\nx=%f  y=%f\nrastojanje=%f\n",p->x,p->y,rastojanje(p->x,p->y));
  125.         printf("--------------------------------------\n");
  126.     }
  127. }
  128.  
  129. int main()
  130. {
  131.     struct tree *p;
  132.     int n;
  133.     scanf("%d",&n);
  134.     p=form(n);
  135.     ispis(p);
  136.     return 0;
  137. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top