QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#363056 | #8505. Almost Aligned | ucup-team1191# | WA | 592ms | 34584kb | C++20 | 3.0kb | 2024-03-23 18:07:51 | 2024-03-23 18:07:52 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define TIME (clock() * 1.0 / CLOCKS_PER_SEC)
const int BIG = 1e9 + 239;
// max
vector<pair<ld, pair<int, int>>> cht(vector<pair<int, int>>& ln) {
sort(ln.begin(), ln.end());
vector<pair<ld, pair<int, int>>> ch;
for (const auto& line : ln) {
while (!ch.empty()) {
auto lst = ch.back().second;
if (lst.first == line.first) {
break;
}
ld x = (ld)(lst.second - line.second) / (line.first - lst.first);
if (x > ch.back().first) {
ch.emplace_back(x, line);
break;
}
ch.pop_back();
}
if (ch.empty()) {
ch.emplace_back(make_pair((ld)0.0, line));
continue;
}
}
//cerr << ch.size() << "\n";
return ch;
}
void solve() {
int n;
cin >> n;
vector<pair<int, int>> x(n), y(n);
int mnx = BIG;
int mxx = -BIG;
int mny = BIG;
int mxy = -BIG;
for (int i = 0; i < n; i++) {
cin >> x[i].second >> y[i].second >> x[i].first >> y[i].first;
mnx = min(mnx, x[i].second);
mxx = max(mxx, x[i].second);
mny = min(mny, y[i].second);
mxy = max(mxy, y[i].second);
}
ld ans = ((ll)(mxx - mnx) * (ll)(mxy - mny));
vector<pair<int, int>> xn(n), yn(n);
for (int i = 0; i < n; i++) {
xn[i].first = -x[i].first;
xn[i].second = -x[i].second;
}
for (int i = 0; i < n; i++) {
yn[i].first = -y[i].first;
yn[i].second = -y[i].second;
}
array<vector<pair<ld, pair<int, int>>>, 4> xs;
xs[0] = cht(x);
xs[1] = cht(xn);
xs[2] = cht(y);
xs[3] = cht(yn);
array<int, 4> pos = {0, 0, 0, 0};
array<ld, 4> ev;
auto func = [&](ld x) {
for (int i = 0; i < 4; i++) {
const auto& line = xs[i][pos[i]].second;
ev[i] = line.first * x + line.second;
}
return (ev[0] + ev[1]) * (ev[2] + ev[3]);
};
while (true) {
bool stop = true;
for (int i = 0; i < 4; i++) {
if (pos[i] + 1 < xs[i].size()) {
stop = false;
break;
}
}
if (stop) {
break;
}
ld mn;
int best = -1;
for (int i = 0; i < 4; i++) {
if (pos[i] + 1 < xs[i].size()) {
if (best == -1 || mn > xs[i][pos[i] + 1].first) {
best = i;
mn = xs[i][pos[i] + 1].first;
}
}
}
ans = min(ans, func(mn));
pos[best]++;
}
cout << ans << "\n";
}
int main() {
#ifdef ONPC
freopen("input", "r", stdin);
#endif
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
int t = 1;
//cin >> t;
while (t--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3860kb
input:
4 0 0 10 10 0 0 10 10 10 10 -10 -10 10 0 -20 0
output:
22.22222222222222222029
result:
ok found '22.222222222', expected '22.222222222', error '0.000000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3728kb
input:
3 0 -1 0 2 1 1 1 1 -1 1 -1 1
output:
0.00000000000000000000
result:
ok found '0.000000000', expected '0.000000000', error '-0.000000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 4028kb
input:
3 0 -1 0 -2 1 1 1 1 -1 1 -1 1
output:
4.00000000000000000000
result:
ok found '4.000000000', expected '4.000000000', error '0.000000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3776kb
input:
1 0 0 0 0
output:
0.00000000000000000000
result:
ok found '0.000000000', expected '0.000000000', error '-0.000000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
4 1000000 1000000 -1 -1000000 1000000 -1000000 -1000000 1 -1000000 -1000000 1 1000000 -1000000 1000000 1000000 -1
output:
3999984000031.99995183944702148438
result:
ok found '3999984000032.000000000', expected '3999984000032.000000000', error '0.000000000'
Test #6:
score: -100
Wrong Answer
time: 592ms
memory: 34584kb
input:
1000000 -871226 486657 -467526 31395 -65837 846554 469710 -907814 927993 -45099 713462 -276539 261942 483255 746021 811070 63449 -779486 588838 -413687 812070 -87868 -813499 -420768 112521 -622607 -832012 921368 -182120 517379 -401743 -837524 -685985 337832 643014 135144 12895 326935 -495720 930620 ...
output:
3999986317541.58295583724975585938
result:
wrong answer 1st numbers differ - expected: '3999996000000.0000000', found: '3999986317541.5830078', error = '0.0000024'