QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#466664 | #8505. Almost Aligned | Swarthmore# | WA | 2216ms | 255184kb | C++14 | 7.7kb | 2024-07-08 01:01:23 | 2024-07-08 01:01:23 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ld = long double;
const ld eps = 1e-12;
const ld inf = 1e30;
struct Point {
ld x, y;
explicit Point (ld x_ = 0, ld y_ = 0) : x(x_), y(y_) {}
Point operator+(const Point & rhs) const {
return Point(x + rhs.x, y + rhs.y);
}
Point operator-(const Point & rhs) const {
return Point(x - rhs.x, y - rhs.y);
}
Point operator*(const ld k) const {
return Point(k * x, k * y);
}
Point operator/(const ld k) const {
return Point(x / k, y / k);
}
ld cross(const Point & rhs) const {
return x * rhs.y - y * rhs.x;
}
ld cross(const Point & a, const Point & b) const {
return (a - *this).cross(b - *this);
}
ld dot(const Point & rhs) const {
return x * rhs.x + y * rhs.y;
}
ld dist2() const {
return x * x + y * y;
}
double dist() {
return sqrt(dist2());
}
Point perp() const {
return Point(-y, x);
}
Point unit() {
return (*this)/dist();
}
bool operator<(const Point & other) const {
if (fabs(x - other.x) > eps) return x < other.x;
return y < other.y;
}
bool operator==(const Point & other) const {
return fabs(x - other.x) < eps && fabs(y - other.y) < eps;
}
};
struct Halfplane {
Point p, pq;
long double angle;
int id;
Halfplane() = default;
Halfplane(const Point & a, const Point & b, int id_) : p(a), pq(b-a), id(id_) {
angle = atan2l(pq.y, pq.x);
}
bool out(const Point & r) {
return pq.cross(r-p) < -eps;
}
bool operator<(const Halfplane & e) const {
return angle < e.angle;
}
friend Point inter(const Halfplane & s, const Halfplane & t) {
ld alpha = (t.p - s.p).cross(t.pq) / s.pq.cross(t.pq);
return s.p + (s.pq * alpha);
}
};
struct Line {
mutable ld k, m, p;
int id;
bool operator<(const Line& o) const { return k < o.k; }
bool operator<(ld x) const { return p < x; }
};
struct LineContainer : multiset<Line, less<>> {
ld div(ld a, ld b) {
return a/b;
}
bool isect(iterator x, iterator y) {
if (y == end()) return x->p = inf, 0;
if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
else x->p = div(y->m - x->m, x->k - y->k);
return x->p >= y->p;
}
void add(ld k, ld m, int id) {
auto z = insert({k, m, 0, id}), y = z++, x = y;
while (isect(y, z)) z = erase(z);
if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
while ((y = x) != begin() && (--x)->p >= y->p)
isect(x, erase(y));
}
int query(ld x) {
assert(!empty());
auto l = *lower_bound(x);
return l.id;
}
};
vector<ld> hp_intersect(vector<Halfplane> & H) {
Point box[4] = {
Point(inf, inf),
Point(0, inf),
Point(0, -inf),
Point(inf, -inf)
};
for (int i = 0; i < 4; i++) {
Halfplane aux(box[i], box[(i+1) % 4], -1);
H.push_back(aux);
}
sort(H.begin(), H.end());
deque<Halfplane> dq;
int len = 0;
for (int i = 0; i < int(H.size()); i++) {
while (len > 1 && H[i].out(inter(dq[len-1], dq[len-2]))) {
dq.pop_back();
--len;
}
while (len > 1 && H[i].out(inter(dq[0], dq[1]))) {
dq.pop_front();
--len;
}
if (len > 0 && fabsl(H[i].pq.cross(dq[len-1] . pq)) < eps) {
if (H[i].pq.dot(dq[len-1].pq) < 0) {
// Short not go to this case
return vector<ld>();
}
if (H[i].out(dq[len-1].p)) {
dq.pop_back();
--len;
}
else continue;
}
dq.push_back(H[i]);
++len;
}
while (len > 2 && dq[0].out(inter(dq[len-1], dq[len-2]))) {
dq.pop_back();
--len;
}
while (len > 2 && dq[len-1].out(inter(dq[0], dq[1]))) {
dq.pop_front();
--len;
}
if (len < 3) return vector<ld>();
vector<ld> ret;
for (int i = 0; i+1 < len; i++) {
ret.push_back(inter(dq[i], dq[i+1]).x);
}
ret.push_back(inter(dq[len-1], dq[0]).x);
return ret;
}
struct Event {
ld t;
int axis;
int type;
int id;
bool operator<(const Event & e) {
return t < e.t;
}
};
ld min_quadratic(ld t2, ld t1, ld t0, ld l, ld r) {
if (fabs(t2) < eps) {
return min(t1 * l + t0, t1 * r + t0);
}
ld x = -t1 / (2 * t2);
if (l <= x && x <= r && t2 > 0) {
return t2 * x * x + t1 * x + t0;
} else {
return min(t2 * l * l + t1 * l + t0, t2 * r * r + t1 * r + t0);
}
}
int main() {
int n;
cin >> n;
vector<Point> p(n), v(n);
for (int i = 0; i < n; i++) {
cin >> p[i].x >> p[i].y >> v[i].x >> v[i].y;
}
if (n == 1) {
cout << 0 << endl;
return 0;
}
vector<ld> x[2], y[2];
// Find out intervals
vector<Halfplane> h;
for (int d = 0; d < 2; d++) {
h = vector<Halfplane>(n);
for (int i = 0; i < n; i++) {
h[i].p = Point(0, p[i].x);
h[i].pq = Point(1, v[i].x) * (d == 0 ? 1 : -1);
h[i].angle = v[i].x * (d == 0 ? 1 : -1);
h[i].id = i;
}
x[d] = hp_intersect(h);
}
for (int d = 0; d < 2; d++) {
h = vector<Halfplane>(n);
for (int i = 0; i < n; i++) {
h[i].p = Point(0, p[i].y);
h[i].pq = Point(1, v[i].y) * (d == 0? 1 : -1);
h[i].angle = v[i].y * (d == 0 ? 1 : -1);
h[i].id = i;
}
y[d] = hp_intersect(h);
}
cout << fixed << setprecision(12);
vector<ld> e;
for (int i = 0; i < 2; i++) {
for (auto t : x[i]) {
e.push_back(t);
}
for (auto t : y[i]) {
e.push_back(t);
}
}
sort(e.begin(), e.end());
int x_axis[2], y_axis[2];
x_axis[0] = x_axis[1] = y_axis[0] = y_axis[1] = 0;
for (int i = 1; i < n; i++) {
if (p[i].x > p[x_axis[0]].x) x_axis[0] = i;
if (p[i].x < p[x_axis[1]].x) x_axis[1] = i;
if (p[i].y > p[y_axis[0]].y) y_axis[0] = i;
if (p[i].y < p[y_axis[1]].y) y_axis[1] = i;
}
LineContainer lx[2], ly[2];
for (int i = 0; i < n; i++) {
lx[1].add(-v[i].x, -p[i].x, i);
lx[0].add(v[i].x, p[i].x, i);
ly[1].add(-v[i].y, -p[i].y, i);
ly[0].add(v[i].y, p[i].y, i);
}
ld ans = (p[x_axis[0]].x - p[x_axis[1]].x) * (p[y_axis[0]].y - p[y_axis[1]].y);
ld lastt = 0;
for (int i = 0; i < e.size(); i++) {
ld t = e[i];
if (t < 0) continue;
// cout << t << endl;
if (t > 1e20) {
break;
}
Point vx = v[x_axis[0]] - v[x_axis[1]];
Point vy = v[y_axis[0]] - v[y_axis[1]];
Point px = p[x_axis[0]] - p[x_axis[1]];
Point py = p[y_axis[0]] - p[y_axis[1]];
ld t2 = vx.x * vy.y;// quadratic
ld t1 = vx.x * py.y + vy.y * px.x; // linear
ld t0 = px.x * py.y;
// printf("lastt = %.3lf t = %.3lf xmax = %d xmin = %d ymax = %d ymin = %d\n", lastt, t, x_axis[0], x_axis[1], y_axis[0], y_axis[1]);
// printf("t2 = %.3lf t1 = %.3lf t0 = %.3lf\n", t2, t1, t0);
ans = min(ans, min_quadratic(t2, t1, t0, lastt, t));
// cout << "ans = " << ans << endl;
if (i != e.size() - 1) {
ld t0 = (t + e[i+1]) / 2;
x_axis[0] = lx[0].query(t0);
x_axis[1] = lx[1].query(t0);
y_axis[0] = ly[0].query(t0);
y_axis[1] = ly[1].query(t0);
}
lastt = t;
}
cout << ans << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3920kb
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: 0ms
memory: 3900kb
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: 0ms
memory: 3916kb
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: 0ms
memory: 3856kb
input:
1 0 0 0 0
output:
0
result:
ok found '0.000000000', expected '0.000000000', error '-0.000000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3888kb
input:
4 1000000 1000000 -1 -1000000 1000000 -1000000 -1000000 1 -1000000 -1000000 1 1000000 -1000000 1000000 1000000 -1
output:
3999984000031.999952077866
result:
ok found '3999984000032.000000000', expected '3999984000032.000000000', error '0.000000000'
Test #6:
score: 0
Accepted
time: 2216ms
memory: 255184kb
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:
3999996000000.000000000000
result:
ok found '3999996000000.000000000', expected '3999996000000.000000000', error '0.000000000'
Test #7:
score: 0
Accepted
time: 1888ms
memory: 255028kb
input:
1000000 3663 6989 -2671 9642 9904 -8111 -4995 5797 599 -8323 -9362 -9045 -6740 1530 3072 6531 3681 -6009 593 -7248 -7878 7266 -5191 4871 4007 -3346 -3801 -3512 192 4840 -4026 -1845 6224 -6143 -1857 5659 -5960 4616 9665 655 5532 -1324 -3901 351 -7670 3951 9243 -4678 2931 -115 -5127 -2353 -7500 -7221 ...
output:
400000000.000000000000
result:
ok found '400000000.000000000', expected '400000000.000000000', error '0.000000000'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3912kb
input:
10 -1 19 -2 6 -26 4 -8 0 6 27 0 7 -3 9 -1 -4 4 -5 5 -5 30 -21 -7 6 -23 -6 0 -5 0 19 3 -5 19 -22 -6 -5 -5 9 -2 5
output:
2744.000000000000
result:
ok found '2744.000000000', expected '2744.000000000', error '0.000000000'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3916kb
input:
10 -3 30 6 7 25 -7 -5 -6 21 8 8 6 -5 19 -6 -1 29 14 -4 -8 -18 15 -7 4 -1 -2 6 -4 -9 -23 -9 -10 -17 12 7 -6 28 16 -7 -4
output:
2491.000000000000
result:
ok found '2491.000000000', expected '2491.000000000', error '0.000000000'
Test #10:
score: -100
Wrong Answer
time: 0ms
memory: 3924kb
input:
100 259 401 17 5 145 -361 -30 -7 397 314 23 -29 -53 332 -19 -5 -11 413 4 -29 -152 -336 1 -26 479 -7 17 -5 142 121 3 24 93 -424 6 -16 387 -138 20 6 136 99 3 -19 -168 181 5 -26 416 -259 26 -28 -108 328 -11 15 247 190 -16 0 -446 473 27 -20 -450 -116 3 -23 79 -409 4 -13 -192 184 -18 -27 50 22 23 -7 187 ...
output:
944965.477691850089
result:
wrong answer 1st numbers differ - expected: '951042.0368828', found: '944965.4776919', error = '0.0063894'