rectangle_processor.cpp

//Author: Zlata Dovbyk
//Laboratory work 4. Variant 12

#include "rectangle_processor.h"
#include <iostream>
#include <algorithm>

namespace RectangleProcessor {

    std::vector<Event> events;

    const Point EMPTY_RANGE = {0, -1};

    void read_input() {
        int cx, cy, w, h;
        while (std::cin >> cx >> cy >> w >> h) {
            if (w <= 0 || h <= 0) {
                break;
            } else {
                int x1 = cx - w / 2;
                int x2 = cx + (w - w / 2);
                int y1 = cy - h / 2;
                int y2 = cy + (h - h / 2);
                events.push_back({x1, y1, y2, +1}); //start covering at x1
                events.push_back({x2 + 1, y1, y2, -1}); //stop covering after x2
            }
        }
        std::sort(events.begin(), events.end());
    }

    void update_active_y(int current_x, size_t& event_index, ActiveY& active_y) {
        while (event_index < events.size() && events[event_index].x == current_x) {
            const auto& e = events[event_index];
            for (int y = e.y1; y <= e.y2; ++y) {
                active_y[y] += e.type;
                if (active_y[y] == 0) {
                    active_y.erase(y); //clean up unused y
                }
            }
            ++event_index;
        }
    }

    void update_max_coverage(int current_x, const ActiveY& active_y, 
        std::vector<Point>& max_points, int& max_coverage) {
            for (const auto& y_entry : active_y) {
                if (y_entry.second > 0) {
                    int value = y_entry.second;
                    Point point = {current_x, y_entry.first}; //current point coverage
                    if (value > max_coverage) {
                        max_coverage = value;
                        max_points.clear();
                        max_points.push_back(point);
                    } else if (value == max_coverage) {
                        max_points.push_back(point);
                    }
                }
            }
    }

    void process_scanline(int current_x, size_t& event_index, ActiveY& active_y,
        std::vector<Point>& max_points, int& max_coverage) {
            update_active_y(current_x, event_index, active_y);
            update_max_coverage(current_x, active_y, max_points, max_coverage);
    }

    Point get_x_range() {
        if (events.empty()) return EMPTY_RANGE;
        return {events.front().x, events.back().x};
    }

    void output_result(const std::vector<Point>& points, int max_coverage) {
        std::cout << "*****\n";
        std::cout << points.size() << "\n";
        std::cout << max_coverage << "\n";
        for (const auto& p : points) {
            std::cout << p.first << " " << p.second << "\n";
        }
    }

    void process() {     
        read_input();
        ActiveY active_y;
        std::vector<Point> max_points;
        int max_coverage = 0;
        size_t event_index = 0;

        auto [min_x, max_x] = get_x_range();
        for (int current_x = min_x; current_x <= max_x; ++current_x) {
            process_scanline(current_x, event_index, active_y, max_points, max_coverage);
        }

        output_result(max_points, max_coverage);
    }
}