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

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


Дано N прямоугольников со сторонами, параллельными осям координат. Требуется определить, на сколько частей эти прямоугольники разбивают плоскость (внутри частей не должно быть границ прямоугольников).


Код

#include <iostream>
#include <cstdio>
#include <vector>
#include <list>
#include <queue>
#include <algorithm>
 
using namespace std;
 
vector<int> X,Y;
int posX,posY;
struct rect
{
    int x0,y0;
    int x1,y1;
    rect(){}
    rect(int X0, int Y0, int X1, int Y1)
    {
        x0 = X0;
        y0 = Y0;
        x1 = X1;
        y1 = Y1;
    }
    void input()
    {
        cin>>x0>>y0>>x1>>y1;
        if (x0>x1) swap(x0,x1);
        if (y0>y1) swap(y0,y1);
        X[posX++] = x0; X[posX++] = x1;
        Y[posY++] = y0; Y[posY++] = y1;
    }
    inline bool isInsideX(int x)
    {
        return x0 <= x && x <= x1;
    }
    inline bool isInsideY(int y)
    {
        return y0 <= y && y <= y1;
    }
    bool isInclude(const rect &R)
    {
        return
            isInsideX(R.x0) && isInsideX(R.x1) &&
            isInsideY(R.y0) && isInsideY(R.y1);
    }
};
int n;
int N,M;
vector<rect> mas;
vector<vector<bool> > used;
vector<vector<list<int> > > adj;
void input()
{
    cin>>n;
    mas.resize(n);
    X.resize(2*n); Y.resize(2*n);
    for (int i=0;i<n;i++)
        mas[i].input();
}
inline void UNIQUE(vector<int> &mas)
{
    sort(mas.begin(), mas.end());
    mas.resize(unique(mas.begin(),mas.end()) - mas.begin());
}
void GenAdj()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            rect curRect(X[i],Y[j],X[i+1],Y[j+1]);
            for (int k = 0; k < mas.size(); k++)
            {
                if (mas[k].isInclude(curRect))
                    adj[i][j].push_back(k);
            }
        }
    }   
}
struct point
{
    int x, y;
    point(){}
    point(int X, int Y)
    {
        x = X; y = Y;
    }
};
int moveX[4] = {-1,0,1,0};
int moveY[4] = {0,-1,0,1};
bool correct(int x, int y)
{
    if (x<0 || y<0)
        return false;
    if (x==N || y==M)
        return false;
    return true;
}
void bfs(int x, int y, int &areaAmount)
{
    if (!adj[x][y].empty())
        areaAmount++;
 
    queue<point> q;
    q.push(point(x,y));
    while (!q.empty())
    {
        point cur = q.front(); q.pop();
        for (int i=0;i<4;i++)
        {
            int nX = cur.x + moveX[i];
            int nY = cur.y + moveY[i];
            if (correct(nX, nY) && !used[nX][nY])
            {
                if (adj[x][y] == adj[nX][nY])
                {
                    used[nX][nY] = true;
                    q.push(point(nX,nY));
                }
            }
        }
    }
}
void search()
{
    int areaAmount = 1;
    for (int i=0;i<adj.size();i++)
    {
        for (int j=0;j<adj[i].size();j++)
        {
            if (!used[i][j])
            {
                used[i][j] = true;
                bfs(i,j,areaAmount);
            }
        }
    }
    cout<<areaAmount;
}
void solve()
{
    UNIQUE(X);
    UNIQUE(Y);
    N = X.size() - 1; M = Y.size()-1;
    used = vector<vector<bool> >(N, vector<bool>(N,false));
    adj = vector<vector<list<int> > >(N, vector<list<int> >(M));
    GenAdj();
    search();
}
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
 
    input();
    solve();
    return 0;
}

         

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


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

Комментарии

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