//一道不那么简单的二分;
//代码有点丑,见谅
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll R, n;
struct node
{
ll x, y, w, h;
}a[10010];
bool check(ll mid)
{
ll left = 0, right = 0;
for(int i = 1;i <= n;i++)
{
int x = a[i].x, y = a[i].y, w = a[i].w, h = a[i].h;
if(x >= mid)
right += w * h;
else if(x + w <= mid)
left += w * h;
else
{
left += (mid - x) * h;
right += (x + w - mid) * h;
}
}
if(left < right)
return false;
else
return true;
}
int main()
{
cin >> R >> n;
for(int i = 1;i <= n;i++)
{
ll x, y, w, h;
cin >> x >> y >> w >> h;
a[i] = {x, y, w, h};
}
ll l = 1, r = R;
while(l < r)
{
ll mid = l + r >> 1;
if(check(mid))
r = mid;
else
l = mid + 1;
}
ll mid = l;
ll left = 0, right = 0;
for(int i = 1;i <= n;i++)
{
int x = a[i].x, y = a[i].y, w = a[i].w, h = a[i].h;
if(x >= mid)
right += w * h;
else if(x + w <= mid)
left += w * h;
else
{
left += (mid - x) * h;
right += (x + w - mid) * h;
}
}
ll cha = left - right;
while(1)
{
l++;
left = 0, right = 0;
for(int i = 1;i <= n;i++)
{
int x = a[i].x, y = a[i].y, w = a[i].w, h = a[i].h;
if(x >= l)
right += w * h;
else if(x + w <= l)
left += w * h;
else
{
left += (l - x) * h;
right += (x + w - l) * h;
}
}
if(left - right != cha)
{
cout << l - 1 << endl;
return 0;
}
if(l == R)
{
cout << l << endl;
return 0;
}
}
//cout << l << endl;
return 0;
}
原题链接点不开
?能点开
ok