【noiOJ】p8208

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
代码愚蠢，对二分理解不深刻。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cmath>
 4 using namespace std;
 5 int n;
 6 long long sum,besum;
 7 int  leftt[10001],w[10001],h[10001],top[10001];
 8 void ssum(long long mid)
 9 {
10     int i;
11     for (i=1;i<=n;i++)
12     {
13         if ((leftt[i]+w[i])<=mid)
14             sum+=(w[i]*h[i]);
15         if (leftt[i]>=mid)
16             sum-=(w[i]*h[i]);
17         if (leftt[i]<mid && (leftt[i]+w[i])>mid)
18             sum+=((mid-leftt[i])*(h[i])-(leftt[i]+w[i]-mid)*(h[i]));
19     }
20 }
21 int main()
22 {
23     long long l,r,mid;
24     scanf("%d",&n);
25     int i;
26     for (i=1;i<=n;i++)
27         scanf("%d%d%d%d",&leftt[i],&top[i],&w[i],&h[i]);
28     l=1;r=10000000000;
29     while (l<r)
30     {
31         mid=(l+r)/2;
32         sum=0;
33         ssum(mid);
34         besum=sum;
35         if (sum>=0 || (abs(sum)==abs(besum) && sum>0))
36             r=mid;
37         else
38             l=mid;
39         if (l+1==r)
40         {
41             long long xx,yy;
42             sum=0;
43             ssum(l);
44             xx=sum;
45             sum=0;
46             ssum(r);
47             yy=sum;
48             if (abs(xx)<=abs(yy))
49                 break;
50             else
51                 l=r;
52         break;
53         }
54     }
55     printf("%lld",l);
56     return 0;
57 }

—Anime Otaku Save The World.