QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#363454 | #8505. Almost Aligned | Days_of_Future_Past# | WA | 656ms | 69840kb | C++23 | 3.6kb | 2024-03-23 22:47:03 | 2024-03-23 22:47:05 |
Judging History
answer
#pragma GCC optimize("O3,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 7;
typedef long long LL;
typedef unsigned long long ULL;
#define all(x) ((x).begin()), ((x).end())
#define pb push_back
typedef double D;
struct P {
D x, y;
void print() const{
printf("%.6f %.6f\n", x, y);
}
P operator + (const P & b) const { return P{x + b.x, y + b.y}; }
P operator - (const P & b) const { return P{x - b.x, y - b.y}; }
D operator * (const P & b) const {
return x * b.y - y * b.x;
}
};
P operator * (const D & x, const P & b) { return P{x * b.x, x * b.y}; }
struct L {
P s, d;
bool contains(const P & x) {
return d * (x - s) > 0;
}
};
P intersect(const L & a, const L & b) {
D lambda = (b.s - a.s) * b.d / (a.d * b.d);
return a.s + lambda * a.d;
}
vector<P> uh[2], lh[2];
vector<P> compute_uh(vector<L> & lines) {
sort(lines.begin(), lines.end(), [&](const L & a, const L & b) {
return a.d.y < b.d.y || a.d.y == b.d.y && a.s.x < b.s.x;
});
vector<L> res;
res.pb(L{P{0, 0}, P{0, -1}});
for(int i = 0, j; i < (int)lines.size(); i = j) {
for(j = i; j < (int)lines.size() && lines[i].d.y == lines[j].d.y; j++);
L & l(lines[j - 1]);
while(res.size() >= 2) {
P i = intersect(res.back(), res[res.size() - 2]);
if(!l.contains(i)) {
res.pop_back();
} else {
break;
}
}
res.pb(l);
}
vector<P> uh;
for(int i = 0; i + 1 < (int)res.size(); i++) {
uh.pb(intersect(res[i], res[i + 1]));
}
uh.pb(intersect(res.back(), L{P{1e10, 1e10}, P{0, -1}}));
return uh;
}
D gety(const P & a, const P & b, const D & x) {
return a.y + (b.y - a.y) * (x - a.x) / (b.x - a.x);
}
const int N = 1000011;
int x[N][2], vx[N][2];
int main() {
int n;
scanf("%d", &n);
for(int i = 0; i < n; i++) {
scanf("%d%d%d%d", &x[i][0], &x[i][1], &vx[i][0], &vx[i][1]);
}
for(int d = 0; d < 2; d++) {
vector<L> lines;
for(int i = 0; i < n; i++) {
lines.push_back(L{P{0, x[i][d]}, P{1, vx[i][d]}});
}
uh[d] = compute_uh(lines);
for(int i = 0; i < n; i++) {
lines[i] = L{P{0, -x[i][d]}, P{1, -vx[i][d]}};
}
lh[d] = compute_uh(lines);
for(auto & p : lh[d]) {
p.y = -p.y;
}
/*printf("uh[%d] : \n", d);
for(auto & p : uh[d]) {
p.print();
}
printf("lh[%d] : \n", d);
for(auto & p : lh[d]) {
p.print();
}*/
}
D ans = 1e50;
auto update = [&](const D & x) {
D u[2], d[2];
D res = 1;
for(int d = 0; d < 2; d++) {
int p = lower_bound(uh[d].begin(), uh[d].end(), P{x, 0}, [&](const P & a, const P & b) {return a.x < b.x;}) - uh[d].begin();
p = min(p, (int)uh[d].size() - 1);
p = max(p, 1);
D u = gety(uh[d][p - 1], uh[d][p], x);
p = lower_bound(lh[d].begin(), lh[d].end(), P{x, 0}, [&](const P & a, const P & b) {return a.x < b.x;}) - lh[d].begin();
p = min(p, (int)lh[d].size() - 1);
p = max(p, 1);
D l = gety(lh[d][p - 1], lh[d][p], x);
res *= u - l;
}
ans = min(ans, res);
};
for(int d = 0; d < 2; d++) {
for(auto & p : uh[d]) {
update(p.x);
}
for(auto & p : lh[d]) {
update(p.x);
}
}
printf("%.12f\n", ans);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 6148kb
input:
4 0 0 10 10 0 0 10 10 10 10 -10 -10 10 0 -20 0
output:
22.222222222222
result:
ok found '22.222222222', expected '22.222222222', error '0.000000000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 5972kb
input:
3 0 -1 0 2 1 1 1 1 -1 1 -1 1
output:
0.000000000000
result:
ok found '0.000000000', expected '0.000000000', error '-0.000000000'
Test #3:
score: 0
Accepted
time: 1ms
memory: 5864kb
input:
3 0 -1 0 -2 1 1 1 1 -1 1 -1 1
output:
4.000000000000
result:
ok found '4.000000000', expected '4.000000000', error '0.000000000'
Test #4:
score: 0
Accepted
time: 1ms
memory: 5972kb
input:
1 0 0 0 0
output:
0.000000000000
result:
ok found '0.000000000', expected '0.000000000', error '-0.000000000'
Test #5:
score: 0
Accepted
time: 1ms
memory: 5828kb
input:
4 1000000 1000000 -1 -1000000 1000000 -1000000 -1000000 1 -1000000 -1000000 1 1000000 -1000000 1000000 1000000 -1
output:
3999984000032.000000000000
result:
ok found '3999984000032.000000000', expected '3999984000032.000000000', error '0.000000000'
Test #6:
score: -100
Wrong Answer
time: 656ms
memory: 69840kb
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:
3999988000008.000000000000
result:
wrong answer 1st numbers differ - expected: '3999996000000.0000000', found: '3999988000008.0000000', error = '0.0000020'