/* Накратко перифразирано условие В правоъгълна координатна система (N*N клетки, N<=10000) са разположени две пръчки (RODS), една хоризонтална и една вертикална, всяка с дължина поне две квадратчета и дебелина 1 квадратче. Двете пръчки може и да се застъпват. Дадена е библиотечна функция, която проверява дали даден правоъгълен участък застъпва част или цяла пръчка. Трябва с най-много 100 повиквания на функцията да се определи местоположението и дължината на двете пръчки. ....... ....... .....#. .....#. .###.#. .....#. .....#. ....... Кратко описание на решението Решаваме като извършим 6 двоични търсения. За всяко едно от тях извършваме максимум 15 (lg 10000) операции. Броя на проверките в най-лошия случай достига lg 10000 + 5 (за дадените тестове това достига 90 проверки). Първите 4 двоични търсения извършваме за да ограничим пръчките отгоре, отдолу, отляво и отдясно. След това проверяваме четирите ъглови квадратчета. В зависимост от отговора на функцията имаме 10 възможни случая, които са описани в сорс кода. Двете функции, с които извършваме двоичното търсене намират в даден интервал къде е съответно най-горния (левия) и най-долния (десния) край на пръчка. findend(ffr,fto,c1,c2,h) ffr и fto - начало и край c1 и c2 - другите две координати h : 0-двоичното търсене се извършва хоризонтално 1-двоичното търсене се извършва вертикално Веселин Райчев */ // TO compile, add to linker options crectlib.o #include <stdio.h> #include "crectlib.h" int check1(int x1,int y1,int x2,int y2) { int r; // printf("c %d %d %d %d",x1+1,y1+1,x2,y2); r=rect(y1+1,y2,x1+1,x2); // printf(" = %d\n",r); return r?1:0; } int check(int ffr,int fto,int c1,int c2,int h) { if (fto==ffr) { return 0; } if (h) { return check1(c1,ffr,c2,fto); } return check1(ffr,c1,fto,c2); } int findbeg(int ffr,int fto,int c1,int c2,int h) { if (fto-ffr<=1) { if (check(ffr,fto,c1,c2,h)) { return ffr; } return fto; } { int m; m=(fto+ffr)/2; if (check(ffr,m,c1,c2,h)) { return findbeg(ffr,m,c1,c2,h); } return findbeg(m,fto,c1,c2,h); // if (check(m,fto,c1,c2,h)) { return findbeg(ffr,m,c1,c2,h); } // return findbeg(m,fto,c1,c2,h); } } int findend(int ffr,int fto,int c1,int c2,int h) { if (fto-ffr<=1) { if (check(ffr,fto,c1,c2,h)) { return fto; } return ffr; } { int m; m=(ffr+fto)/2; if (check(m,fto,c1,c2,h)) { return findend(m,fto,c1,c2,h); } return findend(ffr,m,c1,c2,h); } } int decif(int a,int b) { if (a==b) { return a-1; } return a; } int incif(int a,int b) { if (a==b) { return a+1; } return a; } int rep(int hory,int horf,int hort, int verx,int verf,int vert) { report(hory+1,horf+1,hory+1,hort, verf+1,verx+1,vert,verx+1); return 0; } int main(void) { int x1,y1,x2,y2,n; // int hor,horf,hort; // int ver,verf,vert; n = gridsize(); y1 = findbeg(0,n,0,n,1); // === ffr,fto are in y y2 = findend(y1+2,n,0,n,1); x1 = findbeg(0,n,0,n,0); // === ffr,fto are in x x2 = findend(x1+2,n,0,n,0); // printf("%d %d %d %d\n",x1,y1,x2,y2); switch ( (check1(x1,y1,x1+1,y1+1)<<3) + (check1(x2-1,y1,x2,y1+1)<<2) + (check1(x1,y2-1,x1+1,y2)<<1) + (check1(x2-1,y2-1,x2,y2) ) ) { case 0: // + shape rep( findbeg(y1,y2,x1,x1+1,1) , x1,x2, findbeg(x1,x2,y1,y1+1,0) , y1,y2); break; case 1: case 2: break; // impossible case 3: // _|_ shape rep( y2-1 , x1,x2 , findbeg(x1,x2,y1,y1+1,0) , y1, incif( findend(y1,y2-1,x1,x2,1), y2-1)); break; case 4: break; // impossible case 5: // -| shape rep( findbeg(y1,y2,x1,x1+1,1) , x1, incif( findend(x1,x2-1,y1,y2,0), x2-1), x2-1 , y1,y2 ); break; case 6: if (check1(x2-2,y1,x2-1,y1+1)) { // | ^ rep( y1, findbeg(x1,x2,y1,y1+1,0) , x2 , x1, findbeg(y1,y2,x1,x1+1,1) , y2 ); } else { rep( y2-1, x1, findend(x1,x2,y2-1,y2,0) , x2-1, y1, findend(y1,y2,x2-1,x2,1) ); } break; case 7: // _| shape rep( y2-1, x1, incif(findend(x1,x2-1,y2-1,y2,0) , x2-1) , x2-1, y1, incif(findend(y1,y2-1,x2-1,x2,1) , y2-1) ); break; case 8: break; // impossible; case 9: if (check1(x1+1,y1,x1+2,y1+1)) { rep( y1 , x1 , findend(x1,x2,y1,y1+1,0) , x2-1 , findbeg(y1,y2,x2-1,x2,1) , y2 ); } else { rep( y2-1, findbeg(x1,x2,y2-1,y2,0) , x2 , x1 , y1 , findend(y1,y2,x1,x1+1,1) ); } break; case 10: // |- shape rep( findbeg(y1,y2,x2-1,x2,1) , findbeg(x1+1,x2,y1,y2,0) , x2 , x1,y1,y2 ); break; case 11: // |_ shape rep( y2-1, decif( findbeg(x1+1,x2,y2-1,y2,0) , x1+1 ), x2 , x1, y1, incif( findend(y1,y2-1,x1,x1+1,1) ,y2-1) ); break; case 12: // ^|^ shape rep( y1,x1,x2, findbeg(x1,x2,y2-1,y2,0) , decif( findbeg(y1+1,y2,x1,x2,1) , y1+1) , y2 ); break; case 13: // ^| shape rep( y1,x1, incif( findend(x1,x2-1,y1,y1+1,0) , x2-1 ), x2-1, decif( findbeg(y1+1,y2,x2-1,x2,1) , y1+1 ) , y2 ); break; case 14: // |^ shape rep( y1,decif( findbeg(x1+1,x2,y1,y1+1,0) , x1+1) , x2 , x1,decif( findbeg(y1+1,y2,x1,x1+1,1) , y1+1) , y2 ); break; case 15: break; // impossible default: printf("Error\n"); // Internal error (should never happen) } return 0; }