Нужно решить на с++

Question

Нужно решить на с++

Александр Феткуллин Ученик (237), на голосовании 5 месяцев назад

Дано N прямоугольников со сторонами, параллельными осям координат. Требуется определить площадь фигуры, образованной объединением данных прямоугольников.
Входные данные
В первой строке входного файла INPUT.TXT находится число прямоугольников - N. Затем идут N строк, содержащих по 4 числа: x1, y1, x2, y2 - координаты двух противоположных углов прямоугольника. Все координаты – целые числа, не превосходящие по абсолютной величине 10 000. (1 <= N <= 100)
Выходные данные
В выходной файл OUTPUT.TXT выведите одно целое число – площадь фигуры.

Нужно решить методом сжатия координат.
Чтобы проходило все тесты на этом сайте https://acmp.ru/index.asp?main=task&id_task=380

Answer 1

Лови:

 #include  
#include  
#include  
#include  
#include  
 
using namespace std; 
 
struct Event { 
    int x, y1, y2, type; 
    bool operator<(const Event& e) const { 
        return x < e.x; 
    } 
}; 
 
int main() { 
    ifstream fin("INPUT.TXT"); 
    ofstream fout("OUTPUT.TXT"); 
 
    int N; 
    fin >> N; 
    vector events; 
    set y_coords; 
 
    for (int i = 0; i < N; ++i) { 
        int x1, y1, x2, y2; 
        fin >> x1 >> y1 >> x2 >> y2; 
        if (x1 > x2) swap(x1, x2); 
        if (y1 > y2) swap(y1, y2); 
        events.push_back({x1, y1, y2, 1}); 
        events.push_back({x2, y1, y2, -1}); 
        y_coords.insert(y1); 
        y_coords.insert(y2); 
    } 
 
    sort(events.begin(), events.end()); 
 
    vector y_sorted(y_coords.begin(), y_coords.end()); 
    vector count(y_sorted.size() - 1, 0); 
 
    auto find_index = [&](int y) { 
        return lower_bound(y_sorted.begin(), y_sorted.end(), y) - y_sorted.begin(); 
    }; 
 
    long long area = 0; 
    int prev_x = events[0].x; 
 
    for (const auto& event : events) { 
        int curr_x = event.x; 
        long long width = curr_x - prev_x; 
 
        long long height = 0; 
        for (size_t i = 0; i < count.size(); ++i) { 
            if (count[i] > 0) { 
                height += y_sorted[i + 1] - y_sorted[i]; 
            } 
        } 
 
        area += width * height; 
        prev_x = curr_x; 
 
        int y1_index = find_index(event.y1); 
        int y2_index = find_index(event.y2); 
 
        for (int i = y1_index; i < y2_index; ++i) { 
            count[i] += event.type; 
        } 
    } 
 
    fout << area << endl; 
 
    fin.close(); 
    fout.close(); 
 
    return 0; 
}