Drol
Junior Member | Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору Mickey_from_nsk Цитата: Хммм... Если не секрет, а как засекалось время? Какая аппаратная и программная платформа? Какой компилятор, наконец, и опции компиляции? Странные ограничения. Откуда они? Как в многозадачных системах можно уверенно гарантировать время выполнения задачи? | Как они засекали я не в курсе. Я проверяю и тестирую, test.bat файлов, который на верх написал. компилятор один из 4 языков VC++, Delphi, Java, C# Говорят что у них есть решеная программа, которая успевает за 2 секунды совершить. Нужно использовать какой то алгоритм. Я заметил что, при 10000 точек и 10000 примоугольника, программа совершает за 1 секунду. Я применил алгорит на разделения на 2 части масива, то по 10000 и поверку прямоугольников на точки паральено включил. Так же пробывал за раз по 10 прямоугольников проверку на 1 точку. Но покрайнем мере в отличии от простой верхней програмы алгоритмическии не много быстрее работает. к примеру паралельно по 10 прямоугольников 1 точку проверка #include <stdio.h> int main() { int tob[2],pob[2]; int tc[20000][2]; int pr[20000][4]; int o[10],j,i; scanf("%i %i",&tob[0],&pob[0]); tob[1]=-1;pob[1]=-1; if (tob[0]>9) {tob[1]=tob[0]/10;tob[1]=tob[1]*10;} if (pob[0]>9) {pob[1]=pob[0]/10;pob[1]=pob[1]*10;} // Ввод оптом по 20 или по 10 или 1 точек координат o[0]=tob[1]-10; for (i=0; i<tob[0]; ++i) { scanf("%i%i",&tc[i][0],&tc[i][1]); if (i<o[0]) { scanf("%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i", &tc[i+1][0],&tc[i+1][1], &tc[i+2][0],&tc[i+2][1], &tc[i+3][0],&tc[i+3][1], &tc[i+4][0],&tc[i+4][1], &tc[i+5][0],&tc[i+5][1], &tc[i+6][0],&tc[i+6][1], &tc[i+7][0],&tc[i+7][1], &tc[i+8][0],&tc[i+8][1], &tc[i+9][0],&tc[i+9][1], &tc[i+10][0],&tc[i+10][1], &tc[i+11][0],&tc[i+11][1], &tc[i+12][0],&tc[i+12][1], &tc[i+13][0],&tc[i+13][1], &tc[i+14][0],&tc[i+14][1], &tc[i+15][0],&tc[i+15][1], &tc[i+16][0],&tc[i+16][1], &tc[i+17][0],&tc[i+17][1], &tc[i+18][0],&tc[i+18][1], &tc[i+19][0],&tc[i+19][1] ); i=i+19; } else if (i<tob[1]) { scanf("%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i", &tc[i+1][0],&tc[i+1][1], &tc[i+2][0],&tc[i+2][1], &tc[i+3][0],&tc[i+3][1], &tc[i+4][0],&tc[i+4][1], &tc[i+5][0],&tc[i+5][1], &tc[i+6][0],&tc[i+6][1], &tc[i+7][0],&tc[i+7][1], &tc[i+8][0],&tc[i+8][1], &tc[i+9][0],&tc[i+9][1] ); i=i+9; } } // Ввод оптом по 20 или по 10 или 1 прямоугольника координат o[0]=pob[1]-10; for (i=0; i<pob[0]; ++i) { scanf("%i%i%i%i",&pr[i][0],&pr[i][1],&pr[i][2],&pr[i][3]); if (i<o[0]) { scanf("%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i", &pr[i+1][0],&pr[i+1][1],&pr[i+1][2],&pr[i+1][3], &pr[i+2][0],&pr[i+2][1],&pr[i+2][2],&pr[i+2][3], &pr[i+3][0],&pr[i+3][1],&pr[i+3][2],&pr[i+3][3], &pr[i+4][0],&pr[i+4][1],&pr[i+4][2],&pr[i+4][3], &pr[i+5][0],&pr[i+5][1],&pr[i+5][2],&pr[i+5][3], &pr[i+6][0],&pr[i+6][1],&pr[i+6][2],&pr[i+6][3], &pr[i+7][0],&pr[i+7][1],&pr[i+7][2],&pr[i+7][3], &pr[i+8][0],&pr[i+8][1],&pr[i+8][2],&pr[i+8][3], &pr[i+9][0],&pr[i+9][1],&pr[i+9][2],&pr[i+9][3], &pr[i+10][0],&pr[i+10][1],&pr[i+10][2],&pr[i+10][3], &pr[i+11][0],&pr[i+11][1],&pr[i+11][2],&pr[i+11][3], &pr[i+12][0],&pr[i+12][1],&pr[i+12][2],&pr[i+12][3], &pr[i+13][0],&pr[i+13][1],&pr[i+13][2],&pr[i+13][3], &pr[i+14][0],&pr[i+14][1],&pr[i+14][2],&pr[i+14][3], &pr[i+15][0],&pr[i+15][1],&pr[i+15][2],&pr[i+15][3], &pr[i+16][0],&pr[i+16][1],&pr[i+16][2],&pr[i+16][3], &pr[i+17][0],&pr[i+17][1],&pr[i+17][2],&pr[i+17][3], &pr[i+18][0],&pr[i+18][1],&pr[i+18][2],&pr[i+18][3], &pr[i+19][0],&pr[i+19][1],&pr[i+19][2],&pr[i+19][3] ); i=i+19; } else if (i<pob[1]) { scanf("%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i", &pr[i+1][0],&pr[i+1][1],&pr[i+1][2],&pr[i+1][3], &pr[i+2][0],&pr[i+2][1],&pr[i+2][2],&pr[i+2][3], &pr[i+3][0],&pr[i+3][1],&pr[i+3][2],&pr[i+3][3], &pr[i+4][0],&pr[i+4][1],&pr[i+4][2],&pr[i+4][3], &pr[i+5][0],&pr[i+5][1],&pr[i+5][2],&pr[i+5][3], &pr[i+6][0],&pr[i+6][1],&pr[i+6][2],&pr[i+6][3], &pr[i+7][0],&pr[i+7][1],&pr[i+7][2],&pr[i+7][3], &pr[i+8][0],&pr[i+8][1],&pr[i+8][2],&pr[i+8][3], &pr[i+9][0],&pr[i+9][1],&pr[i+9][2],&pr[i+9][3] ); i=i+9; } } // Проверка прямоугольника с точками for (i=0; i<pob[0]; ++i) { o[0]=0;o[1]=0;o[2]=0;o[3]=0;o[4]=0;o[5]=0;o[6]=0;o[7]=0;o[8]=0;o[9]=0; for (j=0;j<tob[0];++j) { if (tc[j][0]>=pr[i][0] && tc[j][0]<=pr[i][2] && tc[j][1]>=pr[i][1] && tc[j][1]<=pr[i][3]) ++o[0]; if (i<pob[1]) { // проверка еще 9 прямоугольника при условии i<pob[1] иначе не проверяй if (tc[j][0]>=pr[i+1][0] && tc[j][0]<=pr[i+1][2] && tc[j][1]>=pr[i+1][1] && tc[j][1]<=pr[i+1][3]) ++o[1]; if (tc[j][0]>=pr[i+2][0] && tc[j][0]<=pr[i+2][2] && tc[j][1]>=pr[i+2][1] && tc[j][1]<=pr[i+2][3]) ++o[2]; if (tc[j][0]>=pr[i+3][0] && tc[j][0]<=pr[i+3][2] && tc[j][1]>=pr[i+3][1] && tc[j][1]<=pr[i+3][3]) ++o[3]; if (tc[j][0]>=pr[i+4][0] && tc[j][0]<=pr[i+4][2] && tc[j][1]>=pr[i+4][1] && tc[j][1]<=pr[i+4][3]) ++o[4]; if (tc[j][0]>=pr[i+5][0] && tc[j][0]<=pr[i+5][2] && tc[j][1]>=pr[i+5][1] && tc[j][1]<=pr[i+5][3]) ++o[5]; if (tc[j][0]>=pr[i+6][0] && tc[j][0]<=pr[i+6][2] && tc[j][1]>=pr[i+6][1] && tc[j][1]<=pr[i+6][3]) ++o[6]; if (tc[j][0]>=pr[i+7][0] && tc[j][0]<=pr[i+7][2] && tc[j][1]>=pr[i+7][1] && tc[j][1]<=pr[i+7][3]) ++o[7]; if (tc[j][0]>=pr[i+8][0] && tc[j][0]<=pr[i+8][2] && tc[j][1]>=pr[i+8][1] && tc[j][1]<=pr[i+8][3]) ++o[8]; if (tc[j][0]>=pr[i+9][0] && tc[j][0]<=pr[i+9][2] && tc[j][1]>=pr[i+9][1] && tc[j][1]<=pr[i+9][3]) ++o[9]; } } printf("%i\n",o[0]); if (i<pob[1]) { printf("%i\n%i\n%i\n%i\n%i\n%i\n%i\n%i\n%i\n",o[1],o[2],o[3],o[4],o[5],o[6],o[7],o[8],o[9]); i=i+9; } } return(0); } |