ACM|矩形分割（二分） ，北京大学ACM/ICPC竞赛训练暑假课
总时间限制:
1000ms
【ACM|矩形分割（二分） ，北京大学ACM/ICPC竞赛训练暑假课】
内存限制:
65536kB
描述
平面上有一个大矩形，其左下角坐标（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
注意：
1.（输出整数n，表示答案应该是直线 x=n。 如果必要的话，x=R也可以是答案。）一开始，并没有太注意这句话。其实它想表达的意思是：N==1，有一个小矩形，此时将不再是小矩形的右边界，而是大矩形的边界R。因为，题目的要求是（大矩形在直线左边的的面积尽可能大）。
2.需要注意，（小矩形两边面积之差最小）的优先级比（要使得大矩形在直线左边的的面积尽可能大）的优先级高。
3.二分到左右面积相等的时候，就可以提前退出循环。
#include
using namespace std;
int N,R,ans=0;
struct node
{
int l1;
int l2;
int t;
int w;
int h;
long long s;
}no[10006];
long long getS(long long x)//求左右小矩形的面积和，原则：左加右减
{
long long sum=0;
for(long long i=1;
i<=N;
i++)
{
if(no[i].l2<=x)
{
sum+=no[i].s;
continue;
}
else if(no[i].l1>=x)
{
sum-=no[i].s;
continue;
}
else
{
sum=sum+(x-no[i].l1)*no[i].h-(no[i].l2-x)*no[i].h;
}
}
return sum;
}
void work()
{
long long l=0;
long long r=R;
long long mid;
while(l<=r)
{
long long mid=l+(r-l)/2;
if( getS(mid)>0 )
r=mid-1;
else if( getS(mid)<0 )
l=mid+1;
else
{
ans=mid;
break;
}
}
ans=l;
}
int main()
{
cin>>R;
cin>>N;
for(long long i=1;
i<=N;
i++)
{
scanf("%d%d%d%d",&no[i].l1,&no[i].t,&no[i].w,&no[i].h);
no[i].l2=no[i].l1+no[i].w;
no[i].s=no[i].w*no[i].h;
}
if(N==1&&no[1].w==1)
{
cout<
推荐阅读
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- 独自一人
- backtracing——|backtracing—— 131. 分割回文串
- 黄金分割
- 关于蘑菇街算法数据流（ACM）实现方案
- 实现tableViewCell分割线(全屏)
- Pytorch图像分割实践|Pytorch自定义层或者模型类
- 2021-03-19面部脂肪填充多久能消肿（ACMETEA是怎么提升成活率？都来看看！）
- 416.|416. 分割等和子集
- 416.分割等和子集
- Android|Android 之 ProgressDialog用法介绍（矩形进度条 和 圆形 进度条）