QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#736417#2582. 物理实验propane0 1963ms7896kbC++205.5kb2024-11-12 10:54:382024-11-12 10:54:39

Judging History

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

  • [2024-11-12 10:54:39]
  • 评测
  • 测评结果:0
  • 用时:1963ms
  • 内存:7896kb
  • [2024-11-12 10:54:38]
  • 提交

answer

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<numeric>
#include<cmath>
#include<set>
#include<iomanip>
using namespace std;
using LL = long long;

template<typename T>
T sign(T x){
    if (x > 0) return 1;
    if (x < 0) return -1;
    return 0;
}

template<typename T>
T abs(T x){
    if (x < 0) x = -x;
    return x;
}

template<typename T> 
T gcd(T a, T b){
    if (b == 0) return a;
    return gcd(b, a % b);
}

struct Point{
    LL x, y;

    Point operator-(Point t){
        return {x - t.x, y - t.y};
    }

    LL operator^(Point t){
        return x * t.y - y * t.x;
    }

    LL operator*(Point t){
        return x * t.x + y * t.y;
    }

    LL len2(){
        return x * x + y * y;
    }

};

struct Fraction{
    __int128_t x, y;
    long double val;

    Fraction(LL _x, LL _y){
        val = _x / sqrtl(_y);
        __int128_t g = abs(gcd(__int128_t(_x) * _x, __int128_t(_y)));
        x = __int128_t(_x) * _x / g;
        x *= sign(_x);
        y = _y / g;
    }

    bool operator<(const Fraction &t) const {
        __int128_t t1 = x / y;
        __int128_t t2 = t.x / t.y;
        if (t1 != t2) return t1 < t2;
        return (x % y) * t.y < y * (t.x % t.y);
    }

    bool operator==(const Fraction &t) const {
        return x == t.x and y == t.y;
    }

};

struct Event{
    Fraction t; int id, type;

    bool operator<(const Event &a) const {
        if (t == a.t) return type < a.type;
        return t < a.t;
    }

};

long double cur_x;
Point v;

long double project(Point a){
    LL dot = a * v;
    return dot / sqrtl(v.len2());
}

long double area(long double y){
    return abs(v.x * y - v.y * cur_x);
}

struct Segment{
    Point a, b;

    long double k() const {
        LL dx = b.x - a.x;
        LL dy = b.y - a.y;
        return sqrtl(dx * dx + dy * dy) / (project(b) - project(a));
    }

    bool operator<(const Segment &t) const {
        long double y1 = a.y + (cur_x - a.x) / (b.x - a.x) * (b.y - a.y);
        long double y2 = t.a.y + (cur_x - t.a.x) / (t.b.x - t.a.x) * (t.b.y - t.a.y);
        return area(y1) < area(y2);
    }

};

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(10);

    int T;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        vector<Segment> seg(n);
        for(int i = 0; i < n; i++){
            cin >> seg[i].a.x >> seg[i].a.y >> seg[i].b.x >> seg[i].b.y;
        }
        Point a, b; long double L;
        cin >> a.x >> a.y >> b.x >> b.y >> L;
        v = b - a;

        vector<Fraction> nums;
        vector<Event> event;
        nums.reserve(2 * n);
        event.reserve(2 * n);
        
        for(int i = 0; i < n; i++){
            auto &[p1, p2] = seg[i];
            vector<Fraction> q;
            for(auto p : {p1, p2}){
                auto vv = p - a;
                LL dot = vv * v;
                nums.push_back(Fraction(dot, v.len2()));
                q.push_back(nums.back());
            }
            if (q[1] < q[0]) swap(q[0], q[1]), swap(p1, p2);
            event.push_back({q[0], i, 1});
            event.push_back({q[1], i, 0});
        }
        sort(nums.begin(), nums.end());
        nums.erase(unique(nums.begin(), nums.end()), nums.end());

        sort(event.begin(), event.end());

        vector<long double> sum(nums.size() - 1);
        vector<long double> len(nums.size() - 1);

        set<Segment> st[2];

        for(int i = 0, j = 0; i + 1 < nums.size(); i++){
            len[i] = nums[i + 1].val - nums[i].val;
            cur_x = nums[i].val;
            while(j < event.size() and (event[j].t == nums[i] and event[j].type == 0)){
                auto [_, id, type] = event[j++];
                st[((seg[id].a - a) ^ v) > 0].erase(seg[id]);
            }
            while(j < event.size() and (event[j].t == nums[i] and event[j].type == 1)){
                auto [_, id, type] = event[j++];
                st[((seg[id].a - a) ^ v) > 0].insert(seg[id]);
            }

            for(int k = 0; k < 2; k++){
                if (!st[k].empty()){
                    sum[i] += st[k].begin()->k() * len[i];
                }
            }
        }

        long double ans = 0, val = 0;
        for(int i = 0, j = 0; i + 1 < nums.size(); i++){
            if (i - 1 >= 0){
                val -= sum[i - 1];
            }
            while(j + 1 < nums.size() and nums[j + 1].val - nums[i].val <= L){
                val += sum[j++];
            }
            long double cur = val;
            if (nums[j].val - nums[i].val < L and j + 1 < nums.size()){
                cur += (L - (nums[j].val - nums[i].val)) / len[j] * sum[j];
            }
            ans = max(ans, cur);
        }
        val = 0;
        for(int i = nums.size() - 1, j = nums.size() - 1; i >= 1; i--){
            if (i < sum.size()){
                val -= sum[i];
            }
            while(j - 1 >= 0 and nums[i].val - nums[j - 1].val <= L){
                val += sum[--j];
            }
            long double cur = val;
            if (nums[i].val - nums[j].val < L and j - 1 >= 0){
                cur += (L - (nums[i].val - nums[j].val)) / len[j - 1] * sum[j - 1];
            }
            ans = max(ans, cur);
        }
        cout << ans << '\n';
    }

}

Details

Tip: Click on the bar to expand more detailed information

Pretests


Final Tests

Test #1:

score: 0
Wrong Answer
time: 12ms
memory: 3912kb

input:

100
100
7143 -4407 6148 -4332
-3698 1987 -3674 2827
-2240 -6374 -3784 -6054
149 599 327 597
-2580 -4497 -2820 -4347
9219 -1818 6904 502
-5893 1341 -4357 -1890
-3503 -3287 -1087 -1211
-1579 7118 -229 7556
6456 502 1926 -1748
540 6714 -528 6825
1561 8432 -701 8357
422 6998 -41 7462
-1793 3676 1602 517...

output:

648.7436812169
374.0223192036
270.0970128690
18426.9003219508
653.0455806482
246.7697318533
15343.1969045046
817.6373237405
1243.7315426742
620.5391793394
1320.0566275082
15850.0120024217
1136.9253592359
476.8857542508
414.1898278985
850.8402353573
420.3276238079
18940.1157838223
13045.6202569379
14...

result:

wrong answer wrong answer, 1st numbers differ - expected: '939.774677', found: '648.743681', error = '0.309682'

Test #2:

score: 0
Wrong Answer
time: 1745ms
memory: 7848kb

input:

100
10000
954303 48690 -14339 924721
464270 12166 -1609 433494
873644 42682 -12246 843861
449837 10414 -1919 418980
537496 14550 -6578 506603
552080 15962 -6594 521226
870138 42252 -12332 840332
57161 -702218 -671596 -43163
38907 -433607 -402515 -34409
445719 9913 -1981 414808
399734 5765 -1530 3686...

output:

23150.0520326528
2597377.3743440544
21929.1220367422
2894.0091758986
14332.0000021314
3301.0077128122
54920.3123286033
59402.3738040585
37718.7808486373
54764.0089593469
41083.2028447694
67041.8384994659
5004.0198508159
87518.1198773907
65877.5460490806
71160.2290951981
109205.4922828927
17134.60030...

result:

wrong answer wrong answer, 1st numbers differ - expected: '23150.536873', found: '23150.052033', error = '0.000021'

Test #3:

score: 0
Wrong Answer
time: 1963ms
memory: 7896kb

input:

100
10000
-636684471 -90006000 664665488 86376811
-263230447 -307903883 362658164 -223073366
-575841687 -121133860 614287459 40176834
-258935135 -268238570 347975250 -185982857
-287828480 -521064727 443096738 -422002609
-315452625 -391084040 435133968 -289354496
-560776752 -215271244 624810954 -5458...

output:

13997442.4491123982
17046548.7858703807
30676078.2830813271
7797481.0319371080
24229284.3975380739
13387746.9424728360
11289245.8563040873
73382913.5993977705
44300442.3630925716
57621157.0259574269
16696606.0002884474
18751576.1057519421
92269323.2616159331
22030848.0532682162
78604984.6819502089
2...

result:

wrong answer wrong answer, 1st numbers differ - expected: '13997587.658382', found: '13997442.449112', error = '0.000010'