pslg.rar_All of You

#include <stdio.h> #include <conio.h> struct Point { double x; double y; }; void afisareDCEL(int *dcel,int m,char *mesaj) { printf("----------------------------\n\n"); printf("Afisez DCEL: %s",mesaj); for(int i=1;i<=m;i++) printf("Muchia %d: %d %d %d %d %d %d\n",i,dcel[6*i],dcel[6*i+1],dcel[6*i+2],dcel[6*i+3],dcel[6*i+4],dcel[6*i+5]); } //Functia determinant de ABC double determinant(double xA,double yA,double xB,double yB,double xC,double yC){ double det=xA*yB+xC*yA+xB*yC-xC*yB-xB*yA-xA*yC; return det; } //Functia cadran int cadran(double x,double y){ int c=0; if((x>0)&&(y>=0)) c=1; if((x<=0)&&(y>0)) c=2; if((x<0)&&(y<=0)) c=3; if((x>=0)&&(y<0)) c=4; return c; } //Functia RelOrd ce stabileste daca A1 este dupa A2 in jurul lui A0 int RelOrd(double x1,double y1,double x0,double y0,double x2,double y2){ //printf("Punctul i (%6.2lf,%6.2lf) este in cadranul %d\n",x1,y1,cadran(x1,y1)); //printf("Punctul j (%6.2lf,%6.2lf) este in cadranul %d\n",x2,y2,cadran(x2,y2)); //printf("delta(Pi,O,Pj)=%6.2lf\n",determinant(x1,y1,0,0,x2,y2)); if((cadran(x1-x0,y1-y0)>cadran(x2-x0,y2-y0))||((cadran(x1-x0,y1-y0)==cadran(x2-x0,y2-y0))&&(determinant(x1,y1,x0,y0,x2,y2)>0)))return 1;//A1>A2 else if((cadran(x1-x0,y1-y0)==cadran(x2-x0,y2-y0))&&(determinant(x1,y1,x0,y0,x2,y2)==0))return 0;//A1=A2 else return -1;//A1<A2 if((cadran(x1,y1)==cadran(x2,y2))&&(determinant(x1,y1,0,0,x2,y2)<0)) } int main(int argc, char *argv[]) { printf("Am inceput...\n"); printf("0. Date de intrare (Varfuri, DCEL)\n"); //voi indexa tablourile de la 1 //declar si initializez varfurile (prin coordonate) //adaug valoarea {0,0} pentru a permite indexarea de la 1 Point v[]={{0,0},{-8,1},{8,10},{7,-6},{-15,5},{2,3},{1,12},{5,-10},{3,-5},{-10,-4},{1,-9},{-3,8},{1,7}}; Point M[]={{0,0},{5,5}}; // //declar si initializez tabloul 2-dimensional DCEL //adaug valoarea {0,0,0,0,0,0} pentru a permite indexarea de la 1 int DCEL[][6]={{0,0,0,0,0,0}, {11,4,1,0,13,3}, {12,2,2,5,16,15}, {9,4,0,1,4,1}, {9,10,4,0,17,12}, {10,8,4,7,4,14}, {5,11,3,2,8,7}, {6,11,2,0,18,1}, {5,7,6,3,9,14}, {3,5,6,5,10,16}, {7,3,6,0,8,15}, {1,8,3,4,13,5}, {7,10,0,7,10,5}, {1,11,1,3,17,6}, {7,8,7,3,12,11}, {2,3,0,5,18,9}, {5,12,2,5,6,2}, {1,9,4,1,11,3}, {2,6,2,0,2,7}}; // numarul de varfuri int n=sizeof(v)/sizeof(Point)-1; int i,j,k; printf("Varfuri: n=%d.\n",n); // afisez varfurile for(i=1;i<=n;i++)printf("V(%d)=(%6.2lf,%6.2lf)\n",i,v[i].x,v[i].y); // numarul de muchii int m=sizeof(DCEL)/(6*sizeof(int))-1; printf("Muchii m=%d.\n",m); //afisez DCEL initial int* pointer = &DCEL[0][0]; afisareDCEL(pointer,m,"DCEL initial\n"); printf("1. Pasul 1 (renumerotarea varfurilor)\n"); //ordonez varfurile dupa ordonata (coordonata y) int index[n+1]; for(i=1;i<=n;i++)index[i]=i; for(i=1;i<n;i++) for(j=i+1;j<=n;j++) if(v[index[i]].y>v[index[j]].y) { int aux=index[i]; index[i]=index[j]; index[j]=aux; } //afisez regula de schimbare a varfurilor printf("Varfurile se renumeroteaza astfel:"); for(i=1;i<=n;i++)printf("v(%d)->v(%d)\n",index[i],i); for(int l=1;l<=m;l++) { for(i=1;i<=n;i++) { if(DCEL[l][0]==index[i]){DCEL[l][0]=i;break;} } for(i=1;i<=n;i++) { if(DCEL[l][1]==index[i]){DCEL[l][1]=i;break;} } } //afisez DCEL dupa Pasul 1 afisareDCEL(pointer,m,"DCEL, dupa pasul 1\n\n"); printf("2. Pasul 2 (reorientarea muchiilor)\n"); for(i=1;i<=m;i++) if(DCEL[i][0]>DCEL[i][1]) { int aux; // interschimbam V1 cu V2 din DCEL aux=DCEL[i][0]; DCEL[i][0]=DCEL[i][1]; DCEL[i][1]=aux; // interschimbam F1 cu F2 din DCEL aux=DCEL[i][2]; DCEL[i][2]=DCEL[i][3]; DCEL[i][3]=aux; // interschimbam P1 cu P2 din DCEL aux=DCEL[i][4]; DCEL[i][4]=DCEL[i][5]; DCEL[i][5]=aux; } //afisare DCEL dupa Pasul 2 afisareDCEL(pointer,m,"DCEL, dupa pasul 2\n\n"); printf("3. Pasul 3 (obtinerea multimilor Ai si Bi)\n"); int a[13][19]; int b[13][19]; for(i=0;i<13;i++) for(j=0;j<19;j++) {a[i][j]=0;b[i][j]=0;} // primul index este de la 1, iar al doilea index este de la 0 for(int l=1;l<=m;l++) for(i=1;i<=n;i++) { if(DCEL[l][0]==i){b[i][0]+=1;b[i][b[i][0]]=l;} if(DCEL[l][1]==i){a[i][0]+=1;a[i][a[i][0]]=l;} } //afisam muchiile din A(i) BRUTE for(i=1;i<=n;i++) for(j=0;j<=a[i][0];j++) { if(j==0)printf("\nVarianta BRUTA: A[%d] are %d muchii:\n",i,a[i][j]); if(j==a[i][0])printf("%d\n",a[i][j]); if((j>0)&&(j<a[i][0]))printf("%d,",a[i][j]); } //afisam muchiile din B(i) BRUTE for(i=1;i<=n;i++) for(j=0;j<=b[i][0];j++) { if(j==0)printf("\nVarianta BRUTA: B[%d] are %d muchii:\n",i,b[i][j]); if(j==b[i][0])printf("%d\n",b[i][j]); if((j>0)&&(j<b[i][0]))printf("%d,",b[i][j]); } //ordonam varfurile dupa ordonata for(i=1;i<n;i++) for(j=i+1;j<=n;j++) if(v[i].y>v[j].y) { double auxv=v[i].x; v[i].x=v[j].x; v[j].x=auxv; auxv=v[i].y; v[i].y=v[j].y; v[j].y=auxv; } //ordonam muchiile din A(i) cu ajutorul relatiei de ordine (de la PC) for(i=1;i<=n;i++) if(a[i][0]>1) for(j=1;j<=a[i][0]-1;j++) for(k=j+1;k<=a[i][0];k++) { if(RelOrd(v[DCEL[a[i][j]][0]].x,v[DCEL[a[i][j]][0]].y,v[i].x,v[i].y,v[DCEL[a[i][k]][0]].x,v[DCEL[a[i][k]][0]].y)>0) { int aux=a[i][j]; a[i][j]=a[i][k]; a[i][k]=aux; } } //ordonam muchiile din B(i) cu ajutorul relatiei de ordine RelOrd (de la Poligonul Convex) for(i=1;i<=n;i++) if(b[i][0]>1) for(j=1;j<=b[i][0]-1;j++) for(k=j+1;k<=b[i][0];k++) { if(RelOrd(v[DCEL[b[i][j]][1]].x,v[DCEL[b[i][j]][1]].y,v[i].x,v[i].y,v[DCEL[b[i][k]][1]].x,v[DCEL[b[i][k]][1]].y)<0) { int aux=b[i][j]; b[i][j]=b[i][k]; b[i][k]=aux; } } //afisam muchiile din A(i) BUNE - ordonate in sens direct trigonometric for(i=1;i<=n;i++) for(j=0;j<=a[i][0];j++) { if(j==0)printf("\nVarianta BUNA: A[%d] are %d muchii: ",i,a[i][j]); if(j==a[i][0])printf("%d\n",a[i][j]); if((j>0)&&(j<a[i][0]))printf("%d,",a[i][j]); } //afisam muchiile din B(i) BUNE - ordonate in sens invers trigonometric for(i=1;i<=n;i++) for(j=0;j<=b[i][0];j++) { if(j==0)printf("\nVarianta BUNA: B[%d] are %d muchii: ",i,b[i][j]); if(j==b[i][0])printf("%d\n",b[i][j]); if((j>0)&&(j<b[i][0]))printf("%d,",b[i][j]); } printf("4. Pasul 4 (obtinerea lespezilor Li)\n"); //Construim lespezile L(i), unde i este de la 1 la (n-1) int lespede[12][19]; for(i=0;i<=n-1;i++)for(j=0;j<=m;j++)lespede[i][j]=0; //Construim lespedea L(1) for(j=0;j<=b[1][0];j++)lespede[1][j]=b[1][j]; //Construim celelalte n-2 lespezi for(i=2;i<=n-1;i++) { // copiem lespedea i-1 in lespedea i for(j=0;j<=lespede[i-1][0];j++)lespede[i][j]=lespede[i-1][j]; //numarul muchiilor din noua lespede lespede[i][0]=lespede[i][0]+b[i][0]-a[i][0]; for(j=0;j<=lespede[i-1][0];j++) { //parcurgem de la sfarsit sp