QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#466664#8505. Almost AlignedSwarthmore#WA 2216ms255184kbC++147.7kb2024-07-08 01:01:232024-07-08 01:01:23

Judging History

你现在查看的是最新测评结果

  • [2024-07-08 01:01:23]
  • 评测
  • 测评结果:WA
  • 用时:2216ms
  • 内存:255184kb
  • [2024-07-08 01:01:23]
  • 提交

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'