P11756 [COTS 2014] 土地划分 / KRAVE 题解

10chen01 · 2025-02-20 23:32:31 · 题解

思路

• 对于水平的篱笆，可以用左右边界的横坐标 (lft,rgt) 以及它的纵坐标 y 来保存。

• 对于竖直的篱笆，可以用上下边界的纵坐标 (lft,rgt) 以及它的横坐标 x 来保存。

• 然后将这些边使用 set 进行排序，水平的篱笆放入一个集合 H 里面，竖直的篱笆放入一个集合 V 里面。

• 每创建一个篱笆以及进行查询的时候，先找到 (x,y) 所在的矩形，矩形的左右两边在集合 V 使用 lower_bound(x) 和 upper_bound(x) 查找，矩形的上下两边在集合 H 中使用 lower_bound(y) 和 upper_bound(y) 查找。同时，查找到的边的 lft 和 rgt 边界也要包含 x 与 y ，否则往后继续查找。

• 找到矩形后对矩形就可以分割矩形了。求得面积后，若篱笆是横的放入 H 中，是竖的放入 V 中。

代码

#include <iostream>
#include <set>

using namespace std;

#define int long long

int n, a, b;

struct Edge{
  int lft, rgt; // 线段左右边界
  int weight; // 线段的x/y坐标
  bool operator<(const Edge a) const{
    return this->weight < a.weight || (this->weight == a.weight && (this->lft < a.lft ||
      (this->lft == a.lft && this->rgt < a.rgt)));
  }
  bool operator>(const Edge a) const{
    return this->weight > a.weight || (this->weight == a.weight && (this->lft > a.lft ||
      (this->lft == a.lft && this->rgt > a.rgt)));
  }
  Edge& operator=(const Edge& a) {
    this->lft = a.lft;
    this->rgt = a.rgt;
    this->weight = a.weight;
    return *this;
  }
};

set<Edge> horset; // 水平的线段集合
set<Edge> vertset; // 垂直的线段集合

void splitRect(int x, int y, int d){
  // 求(x,y)所在的矩形的由哪些线段可拼成
  auto leftEdge = vertset.lower_bound({0, b, x});
  leftEdge --;
  while(!((*leftEdge).lft <= y && (*leftEdge).rgt >= y)) leftEdge--; // 寻找合法线段
  auto rightEdge = vertset.upper_bound({0, b, x});
  while(!((*rightEdge).lft <= y && (*rightEdge).rgt >= y)) rightEdge++;
  auto topEdge = horset.upper_bound({0, a, y});
  while(!((*topEdge).lft <= x && (*topEdge).rgt >= x)) topEdge++;
  auto bottomEdge = horset.lower_bound({0, a, y});
  bottomEdge --;
  while(!((*bottomEdge).lft <= x && (*bottomEdge).rgt >= x)) bottomEdge--;
  if(d == 1){
    int S1, S2;
    S1 = ((*rightEdge).weight - (*leftEdge).weight) * ((*topEdge).weight - y);
    S2 = ((*rightEdge).weight - (*leftEdge).weight) * (y - (*bottomEdge).weight);
    cout<<min(S1, S2)<<" "<<max(S1, S2)<<endl;
    horset.insert({(*leftEdge).weight, (*rightEdge).weight, y}); // 把线段插入集合
  }else{
    int S1, S2;
    S1 = ((*topEdge).weight - (*bottomEdge).weight) * ((*rightEdge).weight - x);
    S2 = ((*topEdge).weight - (*bottomEdge).weight) * (x - (*leftEdge).weight);
    cout<<min(S1, S2)<<" "<<max(S1, S2)<<endl;
    vertset.insert({(*bottomEdge).weight, (*topEdge).weight, x});
  }
}

signed main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin>>a>>b;
  cin>>n;
  horset.insert({0, a, 0}); // 预先插入四条边界
  horset.insert({0, a, b});
  vertset.insert({0, b, 0});
  vertset.insert({0, b, a});
  for(int i=1;i<=n;i++){
    int x, y, d;
    cin>>x>>y>>d;
    splitRect(x, y, d);
  }
  return 0;
}