Решение задачи Площадь прямоугольников с Меньшиков

Без пояснения   Просмотров: 158


Дано N прямоугольников со сторонами, параллельными осям координат. Требуется определить площадь фигуры, образованной объединением данных прямоугольников.


Код

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
vector<int> X,Y;
void Add(vector<int> &mas , int value)
{
    vector<int>::iterator it = lower_bound(mas.begin(),mas.end(),value);
    if (it == mas.end() || *it != value)
        mas.insert(it,value);
}
 
// оси координат вправо и вниз
struct RECT
{
    int x0,y0; // левый верхний угол
    int x1,y1; // правый нижний угол
    void input()
    {
        int _x0,_y0,_x1,_y1;
        scanf("%d %d %d %d",&_x0, &_y0, &_x1, &_y1);
        if (_x0 > _x1) swap(_x0,_x1);
        if (_y0 > _y1) swap(_y0,_y1);
        init(_x0,_y0,_x1,_y1);
        Add(X,_x0); Add(X,_x1);
        Add(Y,_y0); Add(Y,_y1);
    }
    void init(int _x0, int _y0, int _x1, int _y1)
    {
        x0 = _x0;
        y0 = _y0;
        x1 = _x1;
        y1 = _y1;
    }
    inline bool isInside(int left, int value, int right)
    {
        return left <= value && value <=right;
    }
    bool isParentFor(const RECT &r)
    {
        return isInside(x0,r.x0,x1) &&
               isInside(x0,r.x1,x1) &&
               isInside(y0,r.y0,y1) &&
               isInside(y0,r.y1,y1);       
    }
    int Square()
    {
        return (x1 - x0) * (y1 - y0);
    }
};
int n;
vector<RECT> rects;
void input()
{
    cin>>n;
    rects.resize(n);
    for (int i=0;i<n;i++)
    {
        RECT rect;
        rect.input();
        rects[i] = rect;
    }
}
void solve()
{
    int totalS = 0;
    RECT curRect;
    for (size_t i=0;i<X.size()-1;i++)
    {
        for (size_t j=0;j<Y.size()-1;j++)
        {
            curRect.init(X[i],Y[j],X[i+1],Y[j+1]);
            for (size_t k=0;k<rects.size();k++)
            {
                if (rects[k].isParentFor(curRect))
                {
                    totalS += curRect.Square();
                    break;
                }
            }
        }
    }
    cout<<totalS;
}
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
   
    input();
    solve();
    return 0;
}

         

Администратор Photo Автор: Администратор




Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться