QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#368907 | #8507. Clever Cell Choices | PetroTarnavskyi# | RE | 0ms | 0kb | C++20 | 2.7kb | 2024-03-27 17:56:23 | 2024-03-27 17:56:24 |
answer
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;
const db EPS = 1e-6;
db inter(int k0, int b0, int k1, int b1)
{
if(k0 == k1)
return -1e9;
//k0 * x + b0 = k1 * x + b1;
//x(k1 - k0) = b0 - b1;
return 1.0 * (b0 - b1) / (k1 - k0);
}
vector<tuple<db, int, int>> convex(vector<pair<int, int>> lines)
{
//lines.F * x + lines.S
sort(ALL(lines));
vector<tuple<db, int, int>> res;
res.PB({0, lines[0].F, lines[0].S});
FOR(i, 1, SZ(lines))
{
db x = 0;
while(SZ(res))
{
auto [prevX, k0, b0] = res.back();
x = inter(k0, b0, lines[i].F, lines[i].S);
if(x - EPS < prevX)
res.pop_back();
else
break;
}
res.PB({max(0.0, x), lines[i].F, lines[i].S});
}
return res;
}
vector<tuple<db, int, int, int>> solve(vector<PII> lines, int t)
{
auto res1 = convex(lines);
FOR(i, 0, SZ(lines))
{
lines[i].F *= -1;
lines[i].S *= -1;
}
auto res2 = convex(lines);
int i = 0, j = 0;
vector<tuple<db, int, int, int>> res;
int k = get<1>(res1[0]) + get<2>(res2[0]);
int b = get<1>(res1[0]) + get<2>(res2[0]);
res.PB({0, t, k, b});
while(i + 1 < SZ(res1) || j + 1 < SZ(res2))
{
db x;
if((j + 1 == SZ(res2)) || (i + 1 < SZ(res1) && get<0>(res1[i + 1]) < get<0>(res2[j + 1])))
{
x = get<0>(res1[i + 1]);
k += get<1>(res1[i + 1]) - get<1>(res1[i]);
b += get<2>(res1[i + 1]) - get<2>(res1[i]);
i++;
}
else
{
x = get<0>(res2[j + 1]);
k += get<1>(res2[j + 1]) - get<1>(res2[j]);
b += get<2>(res2[j + 1]) - get<2>(res2[j]);
j++;
}
res.PB({x, t, k, b});
}
return res;
}
int a[2], b[2];
pair<db, db> find(db l, db r)
{
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<PII> x(n), y(n);
FOR(i, 0, n)
{
cin >> x[i].S >> y[i].S >> x[i].F >> y[i].F;
}
auto resX = solve(x, 0);
auto resY = solve(y, 1);
a[0] = get<1>(resX[0]);
b[0] = get<2>(resX[0]);
a[1] = get<1>(resY[0]);
b[1] = get<2>(resY[0]);
auto res = resX;
res.insert(res.end(), ALL(resY));
sort(ALL(res));
pair<db, db> ans = find(0, 0);
FOR(i, 0, SZ(res))
{
auto [l, t, ks, bs] = res[i];
a[t] = ks;
b[t] = bs;
db r = (i + 1 == SZ(res) ? 1e10 : get<0>(res[i + 1]));
auto cur = find(l, r);
if(ans.F - EPS < cur.F)
ans = cur;
}
cout << fixed << setprecision(10) << ans.S << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
3 3 #.# ... #.#