#include #include #include typedef struct { int x; int y; char typ; int id; } t_figurka; // Komparátory pro qsort int generic_cmp (int a_primary, int a_secondary, int b_primary, int b_secondary) { if (a_primary != b_primary) return (a_primary < b_primary) ? -1 : 1; else return (a_secondary < b_secondary) ? -1 : (a_secondary > b_secondary) ? 1 : 0; } // Komparátor 1: Primárně x, sekundárně y (stejné x u sebe) int x_first_cmp (const void * a, const void * b) { t_figurka *aa = (t_figurka*)a; t_figurka *bb = (t_figurka*)b; return generic_cmp(aa->x, aa->y, bb->x, bb->y); } // Komparátor 2: Primárně y, sekundárně x int y_first_cmp (const void * a, const void * b) { t_figurka *aa = (t_figurka*)a; t_figurka *bb = (t_figurka*)b; return generic_cmp(aa->y, aa->x, bb->y, bb->x); } // Komparátor 3: Primárně x-y (hlavní diagonála), sekundárně x int diag_cmp (const void * a, const void * b) { t_figurka *aa = (t_figurka*)a; t_figurka *bb = (t_figurka*)b; return generic_cmp(aa->x-aa->y, aa->x, bb->x-bb->y, bb->x); } // Komparátor 4: Primárně x+y (vedlejší diagonála), sekundárně x int antidiag_cmp (const void * a, const void * b) { t_figurka *aa = (t_figurka*)a; t_figurka *bb = (t_figurka*)b; return generic_cmp(aa->x+aa->y, aa->x, bb->x+bb->y, bb->x); } int main() { // 1. Načteme vstup int B, C; scanf("%d %d\n", &B, &C); // Všechny figurky budeme načítat do jednoho pole a budeme je odlišovat pomocí typu t_figurka *figurky = malloc(sizeof(t_figurka) * (B + C)); // 1.1 Bílé for (int i = 0; i < B; i++) { scanf("%d %d\n", &figurky[i].x, &figurky[i].y); figurky[i].typ = 'W'; figurky[i].id = i; } // 1.2 Černé for (int i = B; i < (B+C); i++) scanf("%c %d %d\n", &figurky[i].typ, &figurky[i].x, &figurky[i].y); // To, jestli je nějaká bílá figurka ohrožena, budeme zaznamenávat do pole, // na počátku inicializujeme vše na false bool *ohrozena = malloc(sizeof(bool) * B); for (int i = 0; i < B; i++) ohrozena[i] = false; // 2. Postupně seřadíme horizontálně/vertikálně/po obou diagonálách a projdeme, // přitom si budeme označovat, které bílé figurky jsou ohrožené // 2.1 Stejné x za sebou qsort(figurky, B + C, sizeof(t_figurka), x_first_cmp); for (int i = 0; i < B + C; i++) { if (figurky[i].typ != 'W') continue; // Zajímám se jenom o bílé figurky // Pokud předchozí nebo následující figurka na stejném x je věž -> jsem ohrožen if ((i > 0 && figurky[i-1].typ == 'V' && figurky[i-1].x == figurky[i].x) || (i + 1 < B+C && figurky[i+1].typ == 'V' && figurky[i+1].x == figurky[i].x)) ohrozena[figurky[i].id] = true; } // 2.2 Stejné y za sebou qsort(figurky, B + C, sizeof(t_figurka), y_first_cmp); for (int i = 0; i < B + C; i++) { if (figurky[i].typ != 'W') continue; // Zajímám se jenom o bílé figurky // Pokud předchozí nebo následující figurka na stejném y je věž -> jsem ohrožen if ((i > 0 && figurky[i-1].typ == 'V' && figurky[i-1].y == figurky[i].y) || (i + 1 < B+C && figurky[i+1].typ == 'V' && figurky[i+1].y == figurky[i].y)) ohrozena[figurky[i].id] = true; } // 2.3 Stejné x-y za sebou (hlavní diagonála) qsort(figurky, B + C, sizeof(t_figurka), diag_cmp); for (int i = 0; i < B + C; i++) { if (figurky[i].typ != 'W') continue; // Zajímám se jenom o bílé figurky // Pokud předchozí nebo následující figurka na stejné hlavní diagonále je střelec -> jsem ohrožen if ((i > 0 && figurky[i-1].typ == 'H' && (figurky[i-1].x - figurky[i-1].y == figurky[i].x - figurky[i].y)) || (i + 1 < B+C && figurky[i+1].typ == 'H' && (figurky[i+1].x - figurky[i+1].y == figurky[i].x - figurky[i].y))) ohrozena[figurky[i].id] = true; } // 2.4 Stejné x+y za sebou (hlavní diagonála) qsort(figurky, B + C, sizeof(t_figurka), antidiag_cmp); for (int i = 0; i < B + C; i++) { if (figurky[i].typ != 'W') continue; // Zajímám se jenom o bílé figurky // Pokud předchozí nebo následující figurka na stejné hlavní diagonále je střelec -> jsem ohrožen if ((i > 0 && figurky[i-1].typ == 'H' && (figurky[i-1].x + figurky[i-1].y == figurky[i].x + figurky[i].y)) || (i + 1 < B+C && figurky[i+1].typ == 'H' && (figurky[i+1].x + figurky[i+1].y == figurky[i].x + figurky[i].y))) ohrozena[figurky[i].id] = true; } // 3. Vypíšeme stav ohrožení figurek for (int i = 0; i < B; i++) if (ohrozena[i]) printf("ANO\n"); else printf("NE\n"); return 0; }