前几天参加西安葡萄城的校招面试，发挥挺拉跨的，但没想到一面还是过了，当时面试官问了我一个面试题，感觉挺有意思的，在这记录一下，并手动实现。

问题：
给n个窗口的打开顺序，然后每个窗口的左上角顶点的坐标，和宽高，还有一个光标的坐标。问光标所在位置是哪个窗口，并且这个窗口的可视面积?（窗口与窗口之间重叠后，后打开的窗口会把先打开的窗口覆盖）

问题一找到光标在哪一个窗口？
思路：
根据给定的打开顺序，从后向前遍历，光标是否在当前窗口。

第二个问题求某个窗口的可视面积？
对某个窗口中的数据处理成矩形，用扫描线来做

代码：

//makefile
src = $(wildcard ./*.cpp)
obj = $(patsubst %.cpp, %.o, $(src))
target = app
CC = g++  
$(target): $(obj)
	$(CC) $(obj) -o $(target)

%.o: %.cpp
	$(CC) -c $< -o $@
.PHONY: clean
clean:
	rm -rf $(obj) $(target)

#include <algorithm>
#include <iostream>
#include <memory>
#include <unordered_map>
#include <vector>
#ifndef _VIEWARE_H_
#define _VIEWARE_H_
#define L INT_MIN
#define R INT_MAX
class Windows;
class Line;
class GetFillArea;
class Soultion;

class Windows {
 public:
  Windows() {}
  Windows(int windowsNums)
      : _windowsSize(windowsNums), _worldHeight(100), _worldWidth(100) {
    _worldIndex.first = _worldIndex.second = 0;
  }
  ~Windows() {}
  int _windowsSize;
  int _worldHeight;
  int _worldWidth;
  static std::vector<int> _coordinate;
  std::pair<int, int> _worldIndex;                 //世界坐标原点
  std::vector<std::vector<int>> _worldCoordinate;  //世界坐标点
  void setWindowsSize(int size) { this->_windowsSize = size; }
  void setWorldHeight(int heigth) { this->_worldHeight = heigth; }
  void setWorldWidth(int width) { this->_worldWidth = width; }
  void insertCoordinate(int x, int y, int width, int height);
  int findWindows(int x, int y);
  void buildPartialData(int windowsIndex);  //构造局部矩形内的数据
  void prPartia();
  std::vector<std::vector<int>> _partiaMatrix;
};

class Line {
 public:
  Line(int sx, int sty, int sdy, bool sfla)
      : x(sx), ty(sty), dy(sdy), fla(sfla) {}
  int x, ty, dy;
  bool fla;
  bool operator<(const Line& a) { return x < a.x; }
};

class GetFillArea {
 public:
  GetFillArea() {}
  std::unordered_map<int, int> Len, Lazy, Rson, Lson;
  std::vector<Line> line;
  std::vector<int> _axis;
  void prepareData(std::vector<std::vector<int>>& matrix);
  void buildTree(int k, int Ls, int Rs);
  void updateInterval(int k, int l, int r, int w);
  void pushUp(int k);
  int getFillArea();
  bool isfill = false;
};

class Soultion {
 public:
  Soultion(){};
  int getViewArea(std::vector<std::vector<int>>& Matrix,int x,int y);
};
#endif

#include "Viewarea.h"
std::vector<int> Windows::_coordinate(4, 0);

void Windows::insertCoordinate(int x, int y, int width, int height) {
  this->_coordinate[0] = x;
  this->_coordinate[1] = y;
  this->_coordinate[2] = x + width;
  this->_coordinate[3] = y + height;
  this->_worldCoordinate.push_back(_coordinate);
}

int Windows::findWindows(int x, int y) {
  int Index = -1;
  for (int i = this->_worldCoordinate.size() - 1; i >= 0; i--) {
    if (x >= _worldCoordinate[i][0] && y >= _worldCoordinate[i][1] &&
        x <= _worldCoordinate[i][2] && y <= _worldCoordinate[i][3]) {
      return i;
    }
  }
  return Index;
}

void Windows::buildPartialData(int windowsindex) {
  int _ax = this->_worldCoordinate[windowsindex][0];
  int _ay = this->_worldCoordinate[windowsindex][1];

  int _dx = this->_worldCoordinate[windowsindex][2];
  int _dy = this->_worldCoordinate[windowsindex][3];

  int _bx = _dx;
  int _by = _ay;

  int _cx = _ax;
  int _cy = _dy;

  for (int i = windowsindex + 1; i < this->_worldCoordinate.size(); i++) {
    int ax = this->_worldCoordinate[i][0];
    int ay = this->_worldCoordinate[i][1];

    int dx = this->_worldCoordinate[i][2];
    int dy = this->_worldCoordinate[i][3];

    int bx = dx;
    int by = ay;

    int cx = ax;
    int cy = dy;

    bool isA, isB, isC, isD;
    int vertex = 0;
    isA = isB = isC = isD = false;
    if (ax >= _ax && ay >= _ay && ax <= _dx && ay <= _dy) {
      isA = true;
      vertex++;
    }

    if (bx >= _ax && by >= _ay && bx <= _dx && by <= _dy) {
      isB = true;
      vertex++;
    }

    if (cx >= _ax && cy >= _ay && cx <= _dx && cy <= _dy) {
      isC = true;
      vertex++;
    }

    if (dx >= _ax && dy >= _ay && dx <= _dx && dy <= _dy) {
      isD = true;
      vertex++;
    }

    if (!vertex) {
      continue;
    } else if (vertex == 1) {
      if (isA) {
        this->_coordinate[0] = ax;
        this->_coordinate[1] = ay;
        this->_coordinate[2] = _dx;
        this->_coordinate[3] = _dy;
      } else if (isB) {
        this->_coordinate[0] = _cx;
        this->_coordinate[1] = by;
        this->_coordinate[2] = bx;
        this->_coordinate[3] = _cy;
      } else if (isC) {
        this->_coordinate[0] = cx;
        this->_coordinate[1] = _by;
        this->_coordinate[2] = _bx;
        this->_coordinate[3] = cy;
      } else if (isD) {
        this->_coordinate[0] = _ax;
        this->_coordinate[1] = _ay;
        this->_coordinate[2] = dx;
        this->_coordinate[3] = dy;
      }
      this->_partiaMatrix.push_back(this->_coordinate);
    } else if (vertex == 2) {
      if (isA && isB) {
        this->_coordinate[0] = ax;
        this->_coordinate[1] = ay;
        this->_coordinate[2] = bx;
        this->_coordinate[3] = std::min(dy, _dy);
      } else if (isC && isD) {
        this->_coordinate[0] = cx;
        this->_coordinate[1] = std::max(ay, _ay);
        this->_coordinate[2] = dx;
        this->_coordinate[3] = dy;
      } else if (isA && isC) {
        this->_coordinate[0] = ax;
        this->_coordinate[1] = ay;
        this->_coordinate[2] = std::min(dx, _dx);
        this->_coordinate[3] = cy;
      } else if (isB && isD) {
        this->_coordinate[0] = std::max(ax, _ax);
        this->_coordinate[1] = ay;
        this->_coordinate[2] = dx;
        this->_coordinate[3] = dy;
      } else {
        this->_coordinate[0] = ax;
        this->_coordinate[1] = ay;
        this->_coordinate[2] = dx;
        this->_coordinate[3] = dy;
      }
      this->_partiaMatrix.push_back(this->_coordinate);
    } else {
      this->_coordinate[0] = ax;
      this->_coordinate[1] = ay;
      this->_coordinate[2] = dx;
      this->_coordinate[3] = dy;
      this->_partiaMatrix.push_back(this->_coordinate);
    }
  }
}

void Windows::prPartia() {
  for (auto x : this->_partiaMatrix) {
    std::cout << x[0] << ' ' << x[1] << ' ' << x[2] << ' ' << x[3] << std::endl;
  }
}

void GetFillArea::prepareData(std::vector<std::vector<int>>& matrix) {
  for (auto& Matrix : matrix) {
    Line lf(Matrix[0], Matrix[1], Matrix[3], true);
    Line ls(Matrix[2], Matrix[1], Matrix[3], false);
    this->line.push_back(lf);
    this->line.push_back(ls);
    this->_axis.push_back(Matrix[1]);
    this->_axis.push_back(Matrix[3]);
  }
  if (matrix.empty()) {
    isfill = true;
    return;
  }
  sort(line.begin(), line.end());
  sort(_axis.begin(), _axis.end());

}

void GetFillArea::pushUp(int k) {
  if (Lazy[k]) {
    Len[k] = Rson[k] - Lson[k];
  } else {
    Len[k] = Len[k << 1] + Len[k << 1 | 1];
  }
}

void GetFillArea::buildTree(int k, int Ls, int Rs) {
  Lson[k] = _axis[Ls - 1], Rson[k] = _axis[Rs - 1];
  if (Rs - Ls <= 1) {
    return;
  }
  int MID = (Ls + Rs) >> 1;
  buildTree(k << 1, Ls, MID);
  buildTree(k << 1 | 1, MID, Rs);
}

void GetFillArea::updateInterval(int k, int l, int r, int w) {
  if (Lson[k] >= l && Rson[k] <= r) {
    Lazy[k] += w;
    pushUp(k);
    return;
  }

  if (Rson[k << 1] > l) {
    updateInterval(k << 1, l, r, w);
  }

  if (Lson[k << 1 | 1] < r) {
    updateInterval(k << 1 | 1, l, r, w);
  }

  pushUp(k);
}

int GetFillArea::getFillArea() {
  int fillareas = 0;

  if (isfill) {
    return fillareas;
  }

  buildTree(1, 1, _axis.size());
  for (int i = 0; i < this->line.size() - 1; i++) {
    int pw = line[i].fla ? 1 : -1;
    updateInterval(1, line[i].ty, line[i].dy, pw);
    fillareas += Len[1] * (line[i + 1].x - line[i].x);
  }
  return fillareas;
}

int Soultion::getViewArea(std::vector<std::vector<int>>& Matrix, int x, int y) {
  std::shared_ptr<Windows> windows = std::make_shared<Windows>(Matrix.size());
  std::shared_ptr<GetFillArea> getfill = std::make_shared<GetFillArea>();
  for (auto pos : Matrix) {
    windows->insertCoordinate(pos[0], pos[1], pos[2], pos[3]);
  }
  int _index = windows->findWindows(x, y);
  int allAreas = abs(windows->_worldCoordinate[_index][0] -
                     windows->_worldCoordinate[_index][2]) *
                 abs(windows->_worldCoordinate[_index][1] -
                     windows->_worldCoordinate[_index][3]);
  windows->buildPartialData(_index);
  getfill->prepareData(windows->_partiaMatrix);
  return allAreas - getfill->getFillArea();
}

#include <iostream>
#include <memory>

#include "Viewarea.h"

int main() {
  std::shared_ptr<Soultion> soultion = std::make_shared<Soultion>();
  /*测试数据*/
  std::vector<std::vector<int>> Matrix = {{1, 1, 3, 3}, {1, 1, 1, 1},
                                          {1, 3, 1, 2}, {3, 2, 2, 2},
                                          {4, 4, 2, 2}, {2, 2, 5, 5}};
  /*光标所在位置*/
  int gx, gy;
  gx = 4, gy = 1;

  std::cout << "ViewArea: " << soultion->getViewArea(Matrix, gx, gy) << std::endl;

  return 0;
}