03:切分矩形组
- 总时间限制:
- 1000ms
- 内存限制:
- 65536kB
- 描述
-
给定若干个平行于坐标轴的互不重叠的矩形，矩形的顶点都是整点。要求画一根平行于y轴的直线x=k（k是整数) ，使得这些矩形落在直线两边面积之差最小。
注意：若直线穿过一个矩形，将会把它切成两个部分，分属左右两侧。
- 输入
- 第一行是整数n，表示有n个矩形(0 < n <= 10000)。
接下来是n行，每行表示一个矩形。每行有4个整数left,top,w,h 分别代表矩形左上角横坐标，矩形左上角纵坐标，矩形宽度，矩形高度。0 <= left,top <= 1000000, 0 <= w,h <= 100000。 - 输出
- 输出使得直线 x= k 两边所包含的矩形面积差最小的k。如果有多条直线满足要求，输出最小的k。
- 样例输入
-
2
1 1 100 100
1000 1 100 100 - 样例输出
-
101
代码愚蠢，对二分理解不深刻。#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int n;
long long sum,besum;
int leftt[],w[],h[],top[];
void ssum(long long mid)
{
int i;
for (i=;i<=n;i++)
{
if ((leftt[i]+w[i])<=mid)
sum+=(w[i]*h[i]);
if (leftt[i]>=mid)
sum-=(w[i]*h[i]);
if (leftt[i]<mid && (leftt[i]+w[i])>mid)
sum+=((mid-leftt[i])*(h[i])-(leftt[i]+w[i]-mid)*(h[i]));
}
}
int main()
{
long long l,r,mid;
scanf("%d",&n);
int i;
for (i=;i<=n;i++)
scanf("%d%d%d%d",&leftt[i],&top[i],&w[i],&h[i]);
l=;r=;
while (l<r)
{
mid=(l+r)/;
sum=;
ssum(mid);
besum=sum;
if (sum>= || (abs(sum)==abs(besum) && sum>))
r=mid;
else
l=mid;
if (l+==r)
{
long long xx,yy;
sum=;
ssum(l);
xx=sum;
sum=;
ssum(r);
yy=sum;
if (abs(xx)<=abs(yy))
break;
else
l=r;
break;
}
}
printf("%lld",l);
return ;
}