#include <stdio.h> #define MIN(a,b) (((a)<(b))?(a):(b)) #define MAX(a,b) (((a)>(b))?(a):(b)) #define MAXPLE 100000 //****** zmienne **** struct plemie { long int x1; long int x2; long int y1; long int y2; int flag; //0 - istniejący, 1 - stopiony z innym plemieniem } plemiona[MAXPLE]; //******* proto ************ int cmp_fun(const void* p1, const void* p2); //***** main ******************** int main(void) { long int n; /* 1-100.000 liczba plemion */ // long int x1, x2, y1, y2; /* 0-1000.000 terytorium plemienne x1<x2, y1<y2 */ long int i,j; long int licznik; int stopienie, stopienie_zew; scanf("%ld\n", &n); for(i=0; i<n; i++) // wczytaj pozycje wejściowe scanf("%ld %ld %ld %ld\n", &plemiona[i].x1, &plemiona[i].x2, &plemiona[i].y1, &plemiona[i].y2 ); //sortowanie wg kolejności leksykograficznej qsort(plemiona, n, sizeof(struct plemie), cmp_fun); //********* test ****** // for(i=0;i<n;i++) // printf("ind_we: %ld, %ld %ld %ld %ld, flag: %d\n", i, plemiona[i].x1, plemiona[i].x2, plemiona[i].y1, plemiona[i].y2, plemiona[i].flag); //***************** //sprawdzanko do{ stopienie_zew = 0; for(i=0;i<n;i++) { do { stopienie = 0; for(j = i+1; j<n; j++) if( ! plemiona[j].flag ) { //printf("%ld %ld %ld\n",i,j,plemiona[j].flag); if(plemiona[j].x1 >= plemiona[i].x2) break; if(plemiona[j].y1 < plemiona[i].y2 && plemiona[j].y2 > plemiona[i].y1) { plemiona[i].x1 = MIN(plemiona[i].x1,plemiona[j].x1); plemiona[i].x2 = MAX(plemiona[i].x2,plemiona[j].x2); plemiona[i].y1 = MIN(plemiona[i].y1,plemiona[j].y1); plemiona[i].y2 = MAX(plemiona[i].y2,plemiona[j].y2); plemiona[j].flag = 1; stopienie = 1; stopienie_zew = 1; } } } while(stopienie); } } while (stopienie_zew); //policz ilość państw i wyprowadź licznik = 0; for(i=0;i<n;i++) if( ! plemiona[i].flag ) licznik++; printf("%ld\n", licznik); for(i=0;i<n;i++) if( ! plemiona[i].flag ) printf("%ld %ld %ld %ld\n", plemiona[i].x1, plemiona[i].x2, plemiona[i].y1, plemiona[i].y2 ); return 0; } //************** functions ************************* int cmp_fun(const void* p1, const void* p2) { struct plemie *a = (struct plemie *)p1, *b = (struct plemie*)p2; if( ( a->x1 > b->x1 ) || ( ( a->x1 == b->x1 ) && ( a->x2 > b->x2 ) ) || ( ( a->x1 == b->x1 ) && ( a->x2 == b->x2 ) && (a->y1 > b->y1) ) || ( ( a->x1 == b->x1 ) && ( a->x2 == b->x2 ) && (a->y1 == b->y1) && (a->y2 > b->y2) ) ) return 1; else if( ( a->x1 < b->x1 ) || ( ( a->x1 == b->x1 ) && ( a->x2 < b->x2 ) ) || ( ( a->x1 == b->x1 ) && ( a->x2 == b->x2 ) && (a->y1 < b->y1) ) || ( ( a->x1 == b->x1 ) && ( a->x2 == b->x2 ) && (a->y1 == b->y1) && (a->y2 < b->y2) ) ) return -1; else return 0; } //-------------
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 | #include <stdio.h> #define MIN(a,b) (((a)<(b))?(a):(b)) #define MAX(a,b) (((a)>(b))?(a):(b)) #define MAXPLE 100000 //****** zmienne **** struct plemie { long int x1; long int x2; long int y1; long int y2; int flag; //0 - istniejący, 1 - stopiony z innym plemieniem } plemiona[MAXPLE]; //******* proto ************ int cmp_fun(const void* p1, const void* p2); //***** main ******************** int main(void) { long int n; /* 1-100.000 liczba plemion */ // long int x1, x2, y1, y2; /* 0-1000.000 terytorium plemienne x1<x2, y1<y2 */ long int i,j; long int licznik; int stopienie, stopienie_zew; scanf("%ld\n", &n); for(i=0; i<n; i++) // wczytaj pozycje wejściowe scanf("%ld %ld %ld %ld\n", &plemiona[i].x1, &plemiona[i].x2, &plemiona[i].y1, &plemiona[i].y2 ); //sortowanie wg kolejności leksykograficznej qsort(plemiona, n, sizeof(struct plemie), cmp_fun); //********* test ****** // for(i=0;i<n;i++) // printf("ind_we: %ld, %ld %ld %ld %ld, flag: %d\n", i, plemiona[i].x1, plemiona[i].x2, plemiona[i].y1, plemiona[i].y2, plemiona[i].flag); //***************** //sprawdzanko do{ stopienie_zew = 0; for(i=0;i<n;i++) { do { stopienie = 0; for(j = i+1; j<n; j++) if( ! plemiona[j].flag ) { //printf("%ld %ld %ld\n",i,j,plemiona[j].flag); if(plemiona[j].x1 >= plemiona[i].x2) break; if(plemiona[j].y1 < plemiona[i].y2 && plemiona[j].y2 > plemiona[i].y1) { plemiona[i].x1 = MIN(plemiona[i].x1,plemiona[j].x1); plemiona[i].x2 = MAX(plemiona[i].x2,plemiona[j].x2); plemiona[i].y1 = MIN(plemiona[i].y1,plemiona[j].y1); plemiona[i].y2 = MAX(plemiona[i].y2,plemiona[j].y2); plemiona[j].flag = 1; stopienie = 1; stopienie_zew = 1; } } } while(stopienie); } } while (stopienie_zew); //policz ilość państw i wyprowadź licznik = 0; for(i=0;i<n;i++) if( ! plemiona[i].flag ) licznik++; printf("%ld\n", licznik); for(i=0;i<n;i++) if( ! plemiona[i].flag ) printf("%ld %ld %ld %ld\n", plemiona[i].x1, plemiona[i].x2, plemiona[i].y1, plemiona[i].y2 ); return 0; } //************** functions ************************* int cmp_fun(const void* p1, const void* p2) { struct plemie *a = (struct plemie *)p1, *b = (struct plemie*)p2; if( ( a->x1 > b->x1 ) || ( ( a->x1 == b->x1 ) && ( a->x2 > b->x2 ) ) || ( ( a->x1 == b->x1 ) && ( a->x2 == b->x2 ) && (a->y1 > b->y1) ) || ( ( a->x1 == b->x1 ) && ( a->x2 == b->x2 ) && (a->y1 == b->y1) && (a->y2 > b->y2) ) ) return 1; else if( ( a->x1 < b->x1 ) || ( ( a->x1 == b->x1 ) && ( a->x2 < b->x2 ) ) || ( ( a->x1 == b->x1 ) && ( a->x2 == b->x2 ) && (a->y1 < b->y1) ) || ( ( a->x1 == b->x1 ) && ( a->x2 == b->x2 ) && (a->y1 == b->y1) && (a->y2 < b->y2) ) ) return -1; else return 0; } //------------- |