QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#143261#7027. Machining Disc RotorsSorting#TL 4291ms3876kbC++234.9kb2023-08-21 00:16:292023-08-21 00:16:32

Judging History

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

  • [2023-08-21 00:16:32]
  • 评测
  • 测评结果:TL
  • 用时:4291ms
  • 内存:3876kb
  • [2023-08-21 00:16:29]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
template<class T> void check_min(T &a, const T &b){ a = (a < b) ? a : b; }
template<class T> void check_max(T &a, const T &b){ a = (a > b) ? a : b; }
#define all(x) (x).begin(), (x).end()

typedef long double ld;
template <class T> int sgn(T x) { return (x > 0) - (x < 0); }
template<class T>
struct Point {
    typedef Point P;
    T x, y;
    explicit Point(T x=0, T y=0) : x(x), y(y) {}
    bool operator<(P p) const { return tie(x,y) < tie(p.x,p.y); }
    bool operator==(P p) const { return tie(x,y)==tie(p.x,p.y); }
    P operator+(P p) const { return P(x+p.x, y+p.y); }
    P operator-(P p) const { return P(x-p.x, y-p.y); }
    P operator*(T d) const { return P(x*d, y*d); }
    P operator/(T d) const { return P(x/d, y/d); }
    T dot(P p) const { return x*p.x + y*p.y; }
    T cross(P p) const { return x*p.y - y*p.x; }
    T cross(P a, P b) const { return (a-*this).cross(b-*this); }
    T dist2() const { return x*x + y*y; }
    ld dist() const { return sqrt((ld)dist2()); }
    // angle to x-axis in interval [-pi, pi]
    ld angle() const { return atan2(y, x); }
    P unit() const { return *this/dist(); } // makes dist()=1
    P perp() const { return P(-y, x); } // rotates +90 degrees
    P normal() const { return perp().unit(); }
    // returns point rotated 'a' radians ccw around the origin
    P rotate(ld a) const {
        return P(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a)); }
    friend ostream& operator<<(ostream& os, P p) {
        return os << "(" << p.x << "," << p.y << ")"; }
};




typedef Point<ld> P;
bool circleInter(P a,P b,ld r1,ld r2,pair<P, P>* out) {
    if (a == b) { assert(r1 != r2); return false; }
    P vec = b - a;
    ld d2 = vec.dist2(), sum = r1+r2, dif = r1-r2,
           p = (d2 + r1*r1 - r2*r2)/(d2*2), h2 = r1*r1 - p*p*d2;
    if (sum*sum < d2 || dif*dif > d2) return false;
    P mid = a + vec*p, per = vec.perp() * sqrt(fmax(0, h2) / d2);
    *out = {mid + per, mid - per};
    return true;
}

const int N = 100 + 3;
const ld PI = acos(-1);

int n, r;
Point<ld> centre[N];
ld radius[N];

Point<ld> angle_to_point(ld angle){
    return (Point<ld>{r, 0}).rotate(angle);
}

ld get_angle(Point<ld> p){
    ld ans =  p.angle();
    if(ans < 0)
        ans += 2 * PI;
    if(ans > 2 * PI)
        ans -= 2 * PI;
    return ans;
}

ld dist_angle(ld a, ld b){
    Point<ld> p1 = angle_to_point(a);
    Point<ld> p2 = angle_to_point(b);
    return (p1 - p2).dist();
}

bool contains(ld a, ld b){
    if(a > b)
        swap(a, b);

    vector<ld> to_check{PI, 3 * PI, -PI, -3*PI};
    for(auto x: to_check)
        if(a <= x && x <= b)
            return true;
    return false;
}

ld calc(pair<ld, ld> a, pair<ld, ld> b){
    if(contains(a.first - b.first, a.first - b.second))
        return 2 * r;
    if(contains(a.second - b.first, a.second - b.second))
        return 2 * r;

    ld ans = 0;
    check_max(ans, dist_angle(a.first, b.first));
    check_max(ans, dist_angle(a.first, b.second));
    check_max(ans, dist_angle(a.second, b.first));
    check_max(ans, dist_angle(a.second, b.second));
    return ans;
}

void solve(){
    cin >> n >> r;

    for(int i = 0; i < n; ++i){
        int _x, _y, _r;
        cin >> _x >> _y >> _r;

        radius[i] = _r;
        centre[i] = Point<ld>{_x, _y};
    }

    vector<pair<ld, ld>> angles;
    for(int i = 0; i < n; ++i){
        pair<Point<ld>, Point<ld>> p;
        if(!circleInter(Point<ld>{0, 0}, centre[i], r, radius[i], &p))
            continue;

        ld a1 = get_angle(p.first);
        ld a2 = get_angle(p.second);
        if(a1 > a2)
            swap(a1, a2);
        ld mid = (a1 + a2) / 2;
        Point<ld> p_mid = angle_to_point(mid);
        if((centre[i] - p_mid).dist() <= radius[i]){

        }
        else{
            swap(a1, a2);
        }

        angles.push_back({a1, a2});
    }

    vector<pair<ld, bool>> sweepline;
    for(auto [l, r]: angles){
        // cout << l << " " << r << " l r" << endl; 
        sweepline.push_back({r, true});
        sweepline.push_back({l, false});
        sweepline.push_back({r + 2 * PI, true});
        sweepline.push_back({l + 2 * PI, false});
    }
    sort(all(sweepline));

    vector<pair<ld, ld>> v;
    ld prev = -1;
    for(auto [angle, start]: sweepline){
        if(!start && prev != -1){
            // cout << prev << " " << angle << " prev angle" << endl;
            v.push_back({prev, angle});
        }
        prev = angle;
    }

    ld ans = 0;
    for(int i = 0; i < v.size(); ++i){
        for(int j = 0; j < v.size(); ++j){
            check_max(ans, calc(v[i], v[j]));
        }
    }

    cout << fixed << setprecision(12) << ans << "\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;

    for(int i = 1; i <= t; ++i){
        cout << "Case #" << i << ": ";
        solve();
    }
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 3788kb

input:

1
3 10
0 12 10
11 -6 10
-11 -6 10

output:

Case #1: 18.611654895000

result:

ok 1 cases

Test #2:

score: 0
Accepted
time: 4291ms
memory: 3876kb

input:

5000
3 1000
750 500 625
-250 -625 625
-1000 1000 1000
3 8
-6 -4 5
2 5 5
8 -8 8
1 710
426 -568 994
1 10
-8 6 15
14 931
622 -651 207
-930 438 552
931 890 743
-264 -923 671
889 -315 179
15 761 173
-440 883 81
-938 -310 170
-271 981 91
918 -88 47
136 927 26
903 29 61
-162 936 22
917 129 18
32 595
431 11...

output:

Case #1: 1998.628237512163
Case #2: 15.989025900097
Case #3: 1420.000000000000
Case #4: 19.843134832984
Case #5: 1862.000000000000
Case #6: 1190.000000000000
Case #7: 934.000000000000
Case #8: 542.000000000000
Case #9: 1808.000000000000
Case #10: 1472.000000000000
Case #11: 1790.000000000000
Case #1...

result:

ok 5000 cases

Test #3:

score: -100
Time Limit Exceeded

input:

5000
48 527
-419 -335 761
519 85 1
-47 524 3
301 431 2
489 -193 3
-102 516 2
-69 521 2
526 2 3
68 522 3
507 139 1
490 191 1
514 109 2
388 355 2
203 485 2
-127 510 3
42 524 1
323 414 1
11 526 1
-17 526 3
452 269 3
514 -111 3
94 517 1
525 -27 1
347 396 1
480 215 3
275 447 2
150 504 3
226 475 1
465 -24...

output:

Case #1: 1053.694800690881
Case #2: 1269.660021675118
Case #3: 1143.844334818410
Case #4: 1183.562268928594
Case #5: 1304.000000000000
Case #6: 1173.961249922395
Case #7: 1051.608339700100
Case #8: 1027.719369369271
Case #9: 1314.000000000000
Case #10: 1007.717091814115
Case #11: 1219.559786161210
C...

result: