Considerăm un caroiaj dreptunghiular cu L linii şi C coloane. Liniile sunt numerotate de la 1 la L de sus în jos şi coloanele de la 1 la C, de la stânga la dreapta. Caroiajul este împărţit în L*C pătrate cu latura egală cu două unităţi (2). În fiecare pătrat al caroiajului se găseşte una dintre valorile 0 sau 1. Se cunoaşte o poziţie (i, j) a unuia dintre pătratele caroiajului (1 ≤ i ≤ L, 1 ≤ j ≤ C).

Trebuie construit un cerc care să îndeplinească următoarele proprietăţi:

Centrul cercului să coincidă cu centrul pătratului din poziţia (i, j);
Raza cercului să fie un număr natural nenul;
Diferenţa dintre numărul de valori 1 şi numărul de valori 0 aflate în pătratele acoperite de cerc să fie maximă.

Considerăm că un pătrat este acoperit de cerc dacă pătratul şi cercul au cel puţin un punct comun (aflat pe contur sau în interior). Dacă un pătrat este complet inclus în interiorul cercului se consideră că şi acel pătrat este acoperit de cerc (în figură, cercul desenat “acoperă” inclusiv pătratul din poziţia (3, 4) ). Cercul din figură are raza 3.

Cerința

Determinaţi diferenţa maximă ce se poate obţine cu constrângerile de mai sus.

Date de intrare

Fişierul cerc1.in conţine pe prima linie patru numere naturale L C i şi j separate prin câte un spaţiu, cu semnificaţia din enunţ.

Pe următoarele L linii se găsesc câte C numere naturale din mulţimea {0, 1}, care reprezintă valorile din pătratele caroiajului. Numerele de pe aceste linii nu sunt separate prin spaţii.

Date de ieșire

Fişierul cerc1.out conţine pe prima linie un singur număr întreg reprezentând valoarea maximă a diferenţei cerute.

Restricții și precizări

1 ≤ L, C ≤ 1000
Se recomandă citirea matricei din fişier linie cu linie şi nu element cu element;
Cercul poate avea raza astfel încât să ocupe zone şi în afara caroiajului, dar acele zone nu influenţează valoarea căutată;

Exemplu

cerc1.in

cerc1.out

Explicație

Valoarea maximă, 4 se poate obţine pentru un cerc de rază 3.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Cerc1:

//Marius Nicoli O(N^2)
#include <stdio.h>
#include <algorithm>
#include <vector>
#define DIM 1011

using namespace std;

struct pereche {
    int d;
    char v;
};

vector<int> F[8*DIM*DIM];

pereche B[DIM*DIM], P;

char A[DIM][DIM];
int L, C, X, Y, i, j, dx, dy, k, maxim, R, M, sum,pozMin, pozMax;

inline int modul(int X) {
    return X > 0 ? X : -X;
}

int cmp(const pereche &a, const pereche &b) {
    return a.d < b.d;
}

void sort(pereche *B, int k) {
    pozMin = 2*DIM*DIM;
    pozMax = 0;
    
    for (int i = 1;i<=k; i++) {
        P = B[i];
        F[B[i].d].push_back(B[i].v);
        if (P.d < pozMin)
            pozMin = P.d;
        if (P.d > pozMax)
            pozMax = P.d;
    }
    
    vector<int>::iterator it;
    k = 0;
    for (i=pozMin;i<=pozMax;i++) {
        for (it = F[i].begin();it!=F[i].end();it++) {
            B[++k].v = *it;
            B[k].d = i;
        }
    }
    int q = 1;
}

int main() {
    FILE *f = fopen("cerc1.in","r");
    FILE *g = fopen("cerc1.out","w");
    fscanf(f,"%d %d %d %d\n",&L, &C, &X, &Y);
    for (i=1;i<=L;i++)
        fscanf(f,"%s",A[i]+1);
    fclose(f);
    for (i=1;i<=L;i++)
        for (j=1;j<=C;j++) {
            P.v = A[i][j] - '0';
            if (i == X && j == Y) {
                P.d = 0;
                B[++k] = P;
                continue;
            }
            if (i == X) {
                P.d = (modul (j - Y) << 1) - 1;
                P.d *= P.d;
                B[++k] = P;
                continue;
            }
            if (j == Y) {
                P.d = (modul (i - X) << 1)- 1;
                P.d *= P.d;
                B[++k] = P;
                continue;
            }
            dx = (modul(i - X) << 1) - 1;
            dy = (modul(j - Y) << 1) - 1;
            P.d = dx * dx + dy * dy;
            B[++k] = P;
        }
        
    sort(B, k);
    R = 1;
    
    M = 4 * ((L > C ? L : C) + 1);
    M *= M;
    i = 1;
    maxim = -3000000;
    B[k+1].d = 3000000;
    while (R*R <= M) {
        if (B[i].d <= R*R) {
            sum += (B[i].v == 1 ? 1 : -1);
            i++;
        }
        if (B[i].d > R*R) {
            if (sum > maxim)
                maxim = sum;
            R++;
        }
        if (i > k)
            break;
    }
    fprintf(g,"%d\n",maxim);
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #708 Cerc1

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #708 Cerc1 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #708 Cerc1