题目：平面上有一个大矩形，其左下角坐标（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
输出
输出整数n，表示答案应该是直线 x=n。 如果必要的话，x=R也可以是答案。
样例输入
1000
2
1 1 2 1
5 1 2 1
样例输出
5
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdio>
using namespace std;
struct jx{
    int x,y,w,h;
    float s;
    float area()
    {return w*h;}
};
int cmp(const jx &a,const jx &b)
{
    return a.x<b.x;
}
jx xjx[10001];
int R,n,mid,temp;
long long l,r,xx;
bool bo;
int sum(int xx)
{
    float area1=0,area2=0;
    bo=0;mid=0;
    for(int i=1;i<=n;i++)
    {if(xjx[i].x+xjx[i].w<=xx)
    {
     area1+=xjx[i].s;
     mid=i;
     }
    if(xjx[i].x>xx) area2+=xjx[i].s;
    if(xjx[i].x<xx&&xjx[i].x+xjx[i].w>xx)
    {
     area1+=(xx-xjx[i].x)*xjx[i].h;
     area2+=(xjx[i].x+xjx[i].w-xx)*xjx[i].h;
     bo=1;
     }
     }
     if(area1>area2) return 1;
     else if(area1<area2)return 2;
     else     return 0;
}

int main()
{   
    freopen("jx1.in","r",stdin) ;
    freopen("jx1.out","w",stdout);
    cin>>R>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>xjx[i].x>>xjx[i].y>>xjx[i].w>>xjx[i].h;
        xjx[i].s=xjx[i].area();
        }
    sort(xjx+1,xjx+n+1,cmp);
    l=xjx[1].x;
    r=xjx[n].x+xjx[n].w;
    while(l+1<=r)
    {
        xx=(l+r)/2;
        temp=sum(xx);
        if(temp==1) r=xx-1;
        else if(temp==2) l=xx+1;
        else  break;
        }
    if(bo==1) cout<<xx;   
    else cout<<xjx[mid+1].x;
    fclose(stdin);fclose(stdout);
    return 0;
}

[此贴子已经被作者于2016-8-16 14:16编辑过]

明白了，谢谢！

谢谢！刚看到评分方法，和以前不同了，找了长时间。