• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

c++矩形分割

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

题目描述
平面上有一个大矩形,其左下角坐标(0,0),右上角坐标(R,R)。大矩形内部包含一些小矩形,小矩形都平行于坐标轴且互不重叠。所有矩形的顶点都是整点。要求画一根平行于y轴的直线x=k(k是整数) ,使得这些小矩形落在直线左边的面积必须大于等于落在右边的面积,且两边面积之差最小。并且,要使得大矩形在直线左边的的面积尽可能大。注意:若直线穿过一个小矩形,将会把它切成两个部分,分属左右两侧。

输入
第一行是整数R,表示大矩形的右上角坐标是(R,R) (1 <= R <= 1,000,000)。
接下来的一行是整数N,表示一共有N个小矩形(0 < N <= 10000)。
再接下来有N 行。每行有4个整数,L,T, W 和 H, 表示有一个小矩形的左上角坐标是(L,T),宽度是W,高度是H (0<=L,T <= R, 0 < W,H <= R). 小矩形不会有位于大矩形之外的部分。

输出
输出整数n,表示答案应该是直线 x=n。如果必要的话,x=R也可以是答案。

样例输入
1000
2
1 1 2 1
5 1 2 1

样例输出
5

 

#include <iostream>

#include <cassert>

#include <vector>

#include <map>

#include <iterator>

using namespace std;

class Rectangle
{
public:
int L; // top left x
int T; // top left y
int W; // width
int H; // height
};

int main()
{
const int MAX_R = 1000000;
const int MAX_N = 10000;
vector<Rectangle> rect_vec;
int R, N;

cin >> R;

assert(R>=1 && R<=MAX_R);

cin >> N;

assert(N>=0 && N<=MAX_N); // ??

if (N <= 1)
{
cout << R << endl;
return 0;
}

Rectangle rec;
int min_x = R;
int max_x = 0;
for (int n=1; n<=N; n++)
{
cin >> rec.L >> rec.T >> rec.W >> rec.H;
rect_vec.push_back(rec);

min_x = min(rec.L, min_x);
max_x = max(rec.L+rec.W, max_x);
}

int Sl; // left square of line x = k
int Sr; // right square of line x = k
map<int, int> Sdiff_k_map;

for (int k=min_x; k<=max_x; k++)
{
Sl = 0;
Sr = 0;
for (int i=0; i<N; i++)
{
if (k <= rect_vec[i].L)
{
Sl += 0;
Sr += rect_vec[i].W * rect_vec[i].H;
}
else if(k >= rect_vec[i].L+rect_vec[i].W)
{
Sl += rect_vec[i].W * rect_vec[i].H;
Sr += 0;
}
else if (k > rect_vec[i].L && k < rect_vec[i].L+rect_vec[i].W)
{
Sl += (k - rect_vec[i].L) * rect_vec[i].H;
Sr += (rect_vec[i].L+rect_vec[i].W - k) * rect_vec[i].H;
}
}
Sdiff_k_map[Sl-Sr] = k;
}

map<int, int>::iterator iter;
for(iter=Sdiff_k_map.begin(); iter!=Sdiff_k_map.end(); iter++)
{
if (iter->first >= 0)
{
cout << iter->second << endl;
break;
}
}

return 0;
}


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
C++与C#之辩证:圣人与巨人比较发布时间:2022-07-13
下一篇:
RedhatLinux下使用wget下载oracle12cdatabasesoftware发布时间:2022-07-13
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap