Задача Барок 2

http://mendo.mk/Task.do?id=466

Дали има некој идеја за решение на задачата?

Досега стигнав до ова решение кое поминува само на првите 6 тест случаеви
а на останатите вади runtime error(претпоставувам заради матрицата city)

#include <iostream>  
#include <vector>  
#include <cstring>  
using namespace std;  
   
int main()  
{  
    int L, W;  
    cin >> L >> W;  
   
    int N;  
    cin >> N;  
   
    vector<pair<int, int> > q;  
    int city[L][W];  
    memset(city, 0, sizeof(city));  
   
   
    long long B;  
    cin >> B;  
   
    for(int i=0; i<B; i++){  
        int Ri, Ci;  
        cin >> Ri >> Ci;  
     
        city[Ri-1][Ci-1] = 1;  
   
        q.push_back(make_pair(Ri-1, Ci-1));  
    }  
   
    int months = 0;  
    int dr[] = {1, -1, 0, 0, -1, -1, 1, 1};  
    int dc[] = {0, 0, 1, -1, -1, 1, 1, -1};
   
    long long temp = B;
    B = 0;
    long long counter = 0;
    long long rezultat = temp;
    while(months<N){  
        months++;  
   
        while(counter < temp){  
            int r = q[counter].first;  
            int c = q[counter].second;  
   
            for(int i=0; i<8; i++){  
                int nr = r + dr[i];  
                int nc = c + dc[i];  
   
                if(nr >= 0 && nr < L && nc >= 0 && nc < W && city[nr][nc] == 0){  
                    rezultat++;
                    city[nr][nc] = months + 1;
                    B++;
                    q.push_back(make_pair(nr, nc));
                }  
            }
            counter++;
        }
        temp = temp + B;
        B=0;
           
    }
   
    cout << rezultat << endl;  
    return 0;  
}

Користи Debugger, ќе ти помогне да го најдеш Runtime Errorot

@Perez

Благодарам за одговорот.

Инаку, проверив дека причината за runtime error-от е тоа што неможе да се иницијализира матрица [750000][750000]

Значи, останува да се најди сосема друго решение.

Ти ја имаш решено?

Ха не , но сега ја прочитав задачата... Интересно кај МЕНДО што коа ќе речат дека вајда ќе треба да работите со long long се мисли на некој СТРИНГ да напраиш него ли ете така
long long int
Пробај со string некако нешто нека ти текне ако можеш

This message was edited 1 time. Last update was at 02/08/2017 14:23:55

Можеме барокните згради да ги замислиме како правоаголници кои се шират секој месец во сите четири правци, горе, доле, лево и десно. Според тоа, ако барокната зграда на почетокот се наоѓа на позиција (x, y), тогаш за N месеци таа ќе го зафаќа правоаголникот со горна-лева координата (max(1, x - N), max(1, y - N)) и долна-десна координата (min(WIDTH, x + N), min(HEIGHT, y + N)). Притоа, сметаме дека горното-лево поле има координати (0, 0), а координатниот систем има ширина WIDTH и висина HEIGHT.

Проблемот успешно го сведовме на познатиот геометриски проблем на наоѓање на плоштина на поклопувачи правоаголници, кој можеме да го решиме со помош на line-sweep техниката.

Бидејќи кодот е обемен, го ставив на Pastebin, и може да се најде на следниов линк: https://pastebin.com/unpBwXzs

Повеќе за line-sweep можеш да прочиташ тука: https://www.topcoder.com/community/data-science/data-science-tutorials/line-sweep-algorithms/

This message was edited 1 time. Last update was at 02/08/2017 18:30:47

Благодарам многу за одговорот @despotovski01

Инаку, еве уште едно решение.

Се користи истата идеја за sweep алгоритамот.

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;

// x1 y1: koordinati na gorna leva tocka
// x2 y2: koordinati na dolna desna tocka
struct Rect {
	int x1, y1, x2, y2;
};

struct Segment {
	long long a, b;
};

void toRectangle
(vector<Rect> &rects, int L, int W, int Ri, int Ci, int N){
    Rect t;
    t.x1 = max(1, Ci - N);
    t.y1 = max(1, Ri - N);
    t.x2 = min(W+1, Ci+N+1);
    t.y2 = min(L+1, Ri + N+1);
 
	rects.push_back(t);
}

// Presmetuva vkupna povrsina na pravoagolnici
// opisani so strukturata Rect
long long calculateArea
(vector<Rect> rects){
	// Collect and sort all x "event" values
	std::vector<int> xs;
	for (int i = 0; i < (int)rects.size(); i++){
		xs.push_back(rects[i].x1);
		xs.push_back(rects[i].x2);
	}

sort(xs.begin(), xs.end());

vector<int>::iterator it = unique(xs.begin(), xs.end());
	xs.resize(distance(xs.begin(), it));

// Visit each pair of x "events"
	long long area = 0;
	for(int i = 0; i < xs.size()-1; i++){
		int x = xs[i];
		deque<int> start, end;
		for(int j = 0; j < (int)rects.size(); j++){
			if(rects[j].x1 <= x && rects[j].x2 > x){
				start.push_back(rects[j].y1);
				end.push_back(rects[j].y2);
			}
		}

sort(start.begin(), start.end());
		sort(end.begin(), end.end());

// Compute vertical line intersection.
		int depth = 0;
		Segment s;
		vector<Segment> segs;
		while (!start.empty() || !end.empty()) {
			int y;
			int predepth = depth;
			if (!start.empty() && start.front() <= end.front()) {
				depth++;
				y = start.front();
				start.pop_front();
			} else {
				depth--;
				y = end.front();
				end.pop_front();
			}
			if (predepth == 0) {
				s.a = y;
			} else if (depth == 0) {
				s.b = y;
				segs.push_back(s);
			}
		}
		
		// Compute area between x "events."
		int width = xs[i + 1] - x;
		for(int j = 0; j < (int)segs.size(); j++){
			area += width * (segs[j].b - segs[j].a);
		}
	}

return area;
}

int main ()
{
    int L, W;  
    cin >> L >> W;  
   
    int N;  
    cin >> N;  
   
   
    int B;  
    cin >> B;
	
	vector<Rect> rects;
    for(int i=0; i<B; i++){  
        int Ri, Ci;  
        cin >> Ri >> Ci;
		toRectangle(rects, L, W, Ri, Ci, N);
    }

long long rezultat = calculateArea(rects);

cout << rezultat << endl;
    return 0;
}