/* Picture (IOI 1998 Day 2 Task 1) Copyright (C) 2002 Flavio Chierichetti This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA Il programma legge picture.in da STDIN e scrive picture.out su STDOUT. Soluzione: Calcolare il perimetro della figura 'unione dei rettangoli' (d'ora in poi figura) significa contare i segmenti unitari del perimetro della figura. Inoltre contare i segmenti unitari del perimetro della figura significa sommare i segmenti orizzontali della figura a quelli verticali. Il numero dei segmenti verticali del perimetro della figura e' uguale alla somma dei segmenti verticali della figura presenti in ogni riga. Scandendo una riga e contanto il numero di volte che un segmento fa parte del lato sinistro (di apertura) di un rettangolo e il numero di volte che fa parte del lato destro (di chiusura), possiamo dire che: - Se abbiamo un segmento verticale che apre un rettangolo e, senza contarlo, il numero di aperture e quello di chiusure sono uguali, quel segmento fa parte del perimetro della figura (il fatto che il numero di aperture dei rettangoli sia uguale a quello di chiusure, implica che non ci siano rettangoli 'aperti' che inglobino quello il cui perimetro contiene il segmento che stiamo considerando; quindi quel segmento e' esterno). - Se abbiamo un segmento verticale che chiude un rettangolo e, contandolo, il numero di aperture e quello di chiusure sono uguali, quel segmento fa parte del perimetro della figura (il segmento considerato chiude un rettangolo 'esterno'). Perche' questo sia valido sempre, e' necessario che, nel caso in cui esistano piu' segmenti unitari nello stesso punto di una riga, si prendando in considerazione prima quelli che aprono un nuovo rettangolo e poi quelli che chiudono uno gia' esistente. Questo per evitare di contare il caso in cui si chiuda un rettangolo 'esterno' e se ne apra, senza lasciare nemmeno uno spazio, uno nuovo. Si procede analogalmente per i segmenti orizzontali e il problema e' risolto. Nel codice che segue si utilizzando alcuni "trucchetti" per velocizzare la computazione. Il codice, comunque, ricalca la soluzione appena descritta. */ #include #include enum { NMax = 4999 }; typedef struct { /* b[0] e' inizio del segmento, b[1] la fine d e' la profondita' del segmento v vale 0 se il segmento apre un rettangolo, 1 altrimenti */ int b[2]; int d, v; } segment; int cmp(const void *a, const void *b); long count(segment *A, segment *B); segment H[NMax * 2], V[NMax * 2]; int N; int main(int argc, char *argv[]) { int x[2], y[2]; int i, j; scanf(" %d", &N); for ( i = 0 ; i < N ; i++ ) { scanf(" %d %d %d %d", x, y, x + 1, y + 1); for ( j = 0 ; j < 2 ; j++ ) { H[i * 2 + j].b[0] = x[0]; H[i * 2 + j].b[1] = x[1]; H[i * 2 + j].d = y[j]; H[i * 2 + j].v = j; V[i * 2 + j].b[0] = y[0]; V[i * 2 + j].b[1] = y[1]; V[i * 2 + j].d = x[j]; V[i * 2 + j].v = j; } } N *= 2; qsort(H, N, sizeof(segment), cmp); qsort(V, N, sizeof(segment), cmp); printf("%ld\n", count(V, H) + count(H, V)); return 0; } long count(segment *A, segment *B) { int i, j, c, d; long t; t = 0; for ( i = 0; i < (N - 1) ; i = j ) { c = 0; d = 0; for ( j = 0 ; j < N ; j++ ) { if ( A[j].b[0] <= B[i].d && B[i].d < A[j].b[1] ) { if ( A[j].v ) { /* Fine Rettangolo */ d--; if ( !d ) c++; } else { /* Inizio Rettangolo */ if ( !d ) c++; d++; } } } for ( j = i+1 ; B[i].d == B[j].d ; j++ ); t += (B[j].d - B[i].d) * c; } return t; } int cmp(const void *a, const void *b) { segment A, B; A = *((segment*)a); B = *((segment*)b); if ( A.d == B.d ) return A.v - B.v; else return A.d - B.d; }