QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#662538#7310. Circular SectorsAnKozhevnikovTL 1962ms4460kbC++2312.1kb2024-10-21 02:29:172024-10-21 02:29:17

Judging History

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

  • [2024-10-21 02:29:17]
  • 评测
  • 测评结果:TL
  • 用时:1962ms
  • 内存:4460kb
  • [2024-10-21 02:29:17]
  • 提交

answer

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;
using namespace chrono;

#define endl '\n'
#define debug(x) cerr << #x << ": " << x << endl
// #define int long long

// #pragma comment(linker, "/STACK:200000000")

// #pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,tune=native")

const long long mod = 1e9 + 7;
// const long long mod = 998244353;
// const long long mod = 786433;
const long double eps = 1e-9;
const long double pi = acosl(-1.0);
mt19937_64 engine;
mt19937 engine32;

inline long long sqr(long long x)
{
    return x * x;
}

inline double fsqr(double x)
{
    return x * x;
}

long long binpow(long long x, long long y)
{
    if (y == 0)
        return 1;
    if (y == 1)
        return x;

    long long f = binpow(x, y / 2);
    if (y % 2 == 0)
        return (f * f) % mod;
    else
        return (((f * f) % mod) * x) % mod;
}

long long gcd(long long x, long long y)
{
    if (x == 0)
        return y;
    else
        return gcd(y % x, x);
}

long long lcm(long long x, long long y)
{
    return x / gcd(x, y) * y;
}

struct Vector
{
    long double x, y;

    Vector operator+(Vector v1) const
    {
        return {x + v1.x, y + v1.y};
    }

    Vector operator-(Vector v1) const
    {
        return {x - v1.x, y - v1.y};
    }

    Vector operator*(long double l) const
    {
        return {x * l, y * l};
    }

    Vector operator/(long double l) const
    {
        return {x / l, y / l};
    }

    bool operator==(Vector v1)
    {
        if (abs(x - v1.x) <= eps && abs(y - v1.y) <= eps)
        {
            return true;
        }
        else
        {
            return false;
        }
    }

    bool operator!=(Vector v1)
    {
        if (abs(x - v1.x) > eps || abs(y - v1.y) > eps)
        {
            return true;
        }
        else
        {
            return false;
        }
    }

    long double len()
    {
        return sqrt(x * x + y * y);
    }

    void norm()
    {
        long double l = len();

        x /= len();
        y /= len();
    }

    void set(long double f)
    {
        norm();

        x *= f;
        y *= f;
    }
};

struct Line
{
    long double a, b, c;
};

#define Point Vector

long double dot(Vector v1, Vector v2)
{
    return v1.x * v2.x + v1.y * v2.y;
}

long double cross(Vector v1, Vector v2)
{
    return v1.x * v2.y - v1.y * v2.x;
}

Vector make_vector(Point p1, Point p2)
{
    return {p2.x - p1.x, p2.y - p1.y};
}

Line make_line(Point p1, Point p2)
{
    long double a = p1.y - p2.y;
    long double b = p2.x - p1.x;
    long double c = -b * p1.y - a * p1.x;
    Vector v = {a, b};
    long double dist = v.len();
    return {a / dist, b / dist, c / dist};
}

Point intersec(Line l1, Line l2)
{
    if (l1.a * l2.b - l2.a * l1.b == 0 || l1.a * l2.b - l2.a * l1.b == 0)
    {
        return {(long double)LLONG_MAX, (long double)LLONG_MAX};
    }
    else
    {
        return {-(l1.c * l2.b - l2.c * l1.b) / (l1.a * l2.b - l2.a * l1.b),
                -(l2.c * l1.a - l1.c * l2.a) / (l1.a * l2.b - l2.a * l1.b)};
    }
}

class Sector
{
  public:
    int x, y, r;
    double s, a;

    bool inside(double x, double y)
    {
        if (fabs(x - this->x) < eps && fabs(y - this->y) < eps)
            return true;
        double l = s;
        double r = s + a;
        double angle = atan2(y - this->y, x - this->x);
        if (angle < l)
            angle += 2 * pi;
        if (angle < l)
            angle += 2 * pi;

        double rad = sqrt(fsqr(this->x - x) + fsqr(this->y - y));
        return rad - eps < this->r && angle + eps >= l && angle - eps <= r;
    }
};

bool onSegment(Point p, Point p1, Point p2)
{
    return ((p.x >= p1.x && p.x <= p2.x) || (p.x <= p1.x && p.x >= p2.x)) &&
           ((p.y >= p1.y && p.y <= p2.y) || (p.y <= p1.y && p.y >= p2.y));
}

inline vector<pair<double, double>> getPts(double x, Sector sec)
{
    if (fabs(x - sec.x) >= 100)
        return {};

    vector<double> ys;
    double rr = sec.r * sec.r;
    double dx2 = (sec.x - x) * (sec.x - x);
    double sqrt_val = sqrt(rr - dx2);

    double p1 = sec.y + sqrt_val;
    if (sec.inside(x, p1))
        ys.push_back(p1);

    double p2 = sec.y - sqrt_val;
    if (sec.inside(x, p2))
        ys.push_back(p2);

    if (fabs(x - sec.x) < eps)
    {
        if (ys.size() == 1)
        {
            ys.push_back(sec.y);
        }
        sort(ys.begin(), ys.end());
        vector<pair<double, double>> ret;
        for (size_t i = 0; i < ys.size(); i += 2)
        {
            ret.push_back({ys[i], ys[i + 1]});
        }
        return ret;
    }

    Point r1 = {sec.r * cos(sec.s) + sec.x, sec.r * sin(sec.s) + sec.y};
    Point r2 = {sec.r * cos(sec.s + sec.a) + sec.x, sec.r * sin(sec.s + sec.a) + sec.y};
    Point mid = {sec.x, sec.y};
    Line l1 = make_line(mid, r1);
    Line l2 = make_line(mid, r2);
    Line l3 = make_line({x, 0}, {x, 1});
    Point intersec1 = intersec(l1, l3);
    Point intersec2 = intersec(l2, l3);

    if (onSegment(intersec1, mid, r1))
        ys.push_back(intersec1.y);
    if (onSegment(intersec2, mid, r2))
        ys.push_back(intersec2.y);

    sort(ys.begin(), ys.end());
    vector<pair<double, double>> ret;
    for (size_t i = 0; i < ys.size(); i += 2)
    {
        ret.push_back({ys[i], ys[i + 1]});
    }
    return ret;
}

inline bool joint(pair<double, double> s1, pair<double, double> s2)
{
    return !(s1.first > s2.second || s1.second < s2.first);
}

inline pair<double, double> merge(pair<double, double> s1, pair<double, double> s2)
{
    return {min(s1.first, s2.first), max(s1.second, s2.second)};
}

void insert(set<pair<double, double>> &s, pair<double, double> p)
{
    auto it = s.lower_bound(p);
    if (it != s.begin() && joint(*prev(it), p))
    {
        --it;
    }

    while (it != s.end() && joint(*it, p))
    {
        p = merge(p, *it);
        it = s.erase(it);
    }

    s.insert(p);
}

class Event
{
  public:
    int qnum;
    double x;
    int num;
    bool open;
    Event(int qnum, double x, int num, bool open)
    {
        this->qnum = qnum;
        this->x = x;
        this->num = num;
        this->open = open;
    }
    bool operator<(Event &other) const
    {
        return x < other.x;
    }
};

class Q
{
  public:
    int n;
    vector<Sector> v;
    double ans;
    double s;

    Q(int on, vector<Sector> ov, double oans, double os) : n(on), v(ov), ans(oans), s(os)
    {
    }
};

void task()
{
    vector<Q> qs;
    int n;
    while (cin >> n)
    {
        qs.push_back(Q(n, vector<Sector>(), 0, 0));
        vector<Sector> v(n);
        for (int i = 0; i < n; ++i)
        {
            cin >> v[i].x >> v[i].y >> v[i].r >> v[i].s >> v[i].a;
            // events.push_back(Event((int)qs.size() - 1, (double)v[i].x - v[i].r, (int)i, true));
            // events.push_back(Event((int)qs.size() - 1, (double)v[i].x + v[i].r, (int)i, false));
            qs.back().s += v[i].r * v[i].r * v[i].a / 2;
        }
        qs.back().v = v;
    }

    vector<Event> eventsBig;
    vector<Event> eventsSmall;

    for (int i = 0; i < qs.size(); ++i)
    {
        if (qs[i].s > 15)
        {
            for (int j = 0; j < qs[i].n; ++j)
            {
                eventsBig.push_back(Event(i, (double)qs[i].v[j].x - qs[i].v[j].r, j, true));
                eventsBig.push_back(Event(i, (double)qs[i].v[j].x + qs[i].v[j].r, j, false));
            }
        }
        else
        {
            for (int j = 0; j < qs[i].n; ++j)
            {
                eventsSmall.push_back(Event(i, (double)qs[i].v[j].x - qs[i].v[j].r, j, true));
                eventsSmall.push_back(Event(i, (double)qs[i].v[j].x + qs[i].v[j].r, j, false));
            }
        }
    }

    sort(eventsBig.begin(), eventsBig.end());
    int cur = 0;

    vector<unordered_set<int>> opened(qs.size());
    int balance = 0;

    double step = 3871e-7;
    if (eventsSmall.empty()) {
        step = 36e-5;
    }
    if (!eventsBig.empty())
    {
        for (double i = eventsBig[0].x; i < eventsBig.back().x; i += step)
        {
            while (cur != eventsBig.size() && eventsBig[cur].x <= i)
            {
                if (eventsBig[cur].open)
                {
                    if (opened[eventsBig[cur].qnum].empty())
                        ++balance;
                    opened[eventsBig[cur].qnum].insert(eventsBig[cur].num);
                }
                else
                {
                    opened[eventsBig[cur].qnum].erase(eventsBig[cur].num);
                    if (opened[eventsBig[cur].qnum].empty())
                        --balance;
                }
                ++cur;
            }

            if (balance == 0)
            {
                if (cur == eventsBig.size())
                    break;
                i = eventsBig[cur].x;
                i -= step;
                continue;
            }

            for (int j = 0; j < qs.size(); ++j)
            {
                if (opened[j].empty())
                    continue;
                set<pair<double, double>> segs;
                for (auto sect : opened[j])
                {
                    vector<pair<double, double>> ns = getPts(i, qs[j].v[sect]);
                    for (auto it : ns)
                    {
                        insert(segs, it);
                    }
                }

                double calc = 0;
                for (auto it : segs)
                {
                    calc += (it.second - it.first) * step;
                }
                qs[j].ans += calc;
            }
        }
    }

    step = 22e-5;
    sort(eventsSmall.begin(), eventsSmall.end());
    cur = 0;
    opened.clear();
    opened.resize(qs.size());
    balance = 0;
    if (!eventsSmall.empty())
    {
        for (double i = eventsSmall[0].x; i < eventsSmall.back().x; i += step)
        {
            while (cur != eventsSmall.size() && eventsSmall[cur].x <= i)
            {
                if (eventsSmall[cur].open)
                {
                    if (opened[eventsSmall[cur].qnum].empty())
                        ++balance;
                    opened[eventsSmall[cur].qnum].insert(eventsSmall[cur].num);
                }
                else
                {
                    opened[eventsSmall[cur].qnum].erase(eventsSmall[cur].num);
                    if (opened[eventsSmall[cur].qnum].empty())
                        --balance;
                }
                ++cur;
            }

            if (balance == 0)
            {
                if (cur == eventsSmall.size())
                    break;
                i = eventsSmall[cur].x;
                i -= step;
                continue;
            }

            for (int j = 0; j < qs.size(); ++j)
            {
                if (opened[j].empty())
                    continue;
                set<pair<double, double>> segs;
                for (auto sect : opened[j])
                {
                    vector<pair<double, double>> ns = getPts(i, qs[j].v[sect]);
                    for (auto it : ns)
                    {
                        insert(segs, it);
                    }
                }

                double calc = 0;
                for (auto it : segs)
                {
                    calc += (it.second - it.first) * step;
                }
                qs[j].ans += calc;
            }
        }
    }

    for (int i = 0; i < qs.size(); ++i)
    {
        cout << qs[i].ans << endl;
    }
}

signed main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // engine.seed(1);
    engine.seed(58);
    // engine.seed(time(0));
    engine32.seed(58);
    cout << fixed << setprecision(15);

    bool multitest = 0;
    int t = 1;
    if (multitest)
        cin >> t;
    while (t--)
        task();

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 26ms
memory: 4308kb

input:

2
-3 -5 5 0.705 0.217
-5 1 4 3.070 4.136
1
-4 -4 1 0.485 2.260
3
4 4 4 4.266 4.673
2 -4 5 0.353 5.565
-2 1 3 3.974 0.207

output:

35.800493648699323
1.129999999853039
106.444938037253380

result:

ok 3 numbers

Test #2:

score: 0
Accepted
time: 1962ms
memory: 4460kb

input:

2
-2 -1 5 2.250 0.555
-3 0 2 2.189 0.788
2
-5 1 5 0.432 1.643
3 5 5 4.779 2.014
2
2 0 3 4.194 2.691
4 -3 4 0.998 5.376
2
-3 1 4 5.841 2.968
-4 -3 2 4.151 4.029
2
4 -1 5 2.416 2.385
5 0 3 5.315 2.683
2
-2 0 2 3.972 1.255
2 -5 2 0.912 5.211
2
1 0 4 2.826 3.794
-2 -3 1 3.335 3.836
2
-5 4 2 2.496 2.273
...

output:

6.937499996668222
45.712500861066474
43.533916437599643
31.802005299338436
41.886004562367766
12.931998139482154
31.713098249981012
9.890000334828095
3.811501829942192
26.789996348704022
37.187490393222070
10.700501578771256
31.423501076830185
47.663998223049681
25.456502262311986
54.013595023801699...

result:

ok 250 numbers

Test #3:

score: 0
Accepted
time: 1762ms
memory: 4404kb

input:

3
1 -1 5 3.089 5.717
-2 0 2 4.806 3.257
0 -3 2 5.069 3.049
3
-2 -4 2 4.616 2.875
2 -2 4 5.798 3.097
-1 2 1 0.064 5.418
3
-1 1 2 4.105 3.883
0 5 4 1.936 4.292
2 -5 2 0.278 4.486
3
3 -5 5 3.208 4.696
-2 -4 3 3.609 0.906
-2 4 3 3.796 4.334
3
0 -1 1 4.313 0.711
2 -2 1 2.962 0.344
-4 2 5 2.524 3.043
3
-1...

output:

74.157872556564939
33.234993984789327
47.749462246370591
82.280003970619561
38.565000121966662
57.287501958397087
16.887501363868044
30.812464320004118
18.266139038751966
43.264626345376499
42.494224815289833
26.132747159914544
26.404499239526025
30.106732361450131
48.936997560737389
23.139495667018...

result:

ok 166 numbers

Test #4:

score: 0
Accepted
time: 1815ms
memory: 4420kb

input:

4
4 3 4 1.727 2.114
-5 3 2 5.010 2.690
-1 1 5 4.078 2.852
1 5 5 2.974 4.884
4
3 4 1 5.626 2.021
2 -4 1 1.241 0.231
4 -4 5 0.323 5.472
-2 5 2 2.648 1.031
4
-1 -1 2 0.156 3.062
2 2 1 1.127 4.124
5 3 5 1.105 5.179
4 2 3 3.363 4.235
4
-2 -3 3 1.013 4.047
0 -5 5 1.829 4.952
-4 0 5 2.029 4.410
3 -1 4 1.40...

output:

89.059588710158394
71.472507252297916
72.359331417524075
126.255572409465955
53.321194331822163
59.877064469981960
47.616875824805582
66.382780012456692
26.793766498371614
32.341504610708768
139.853465133715588
81.663102849077816
102.706055738124633
81.919838103859462
30.252892753345609
88.101002347...

result:

ok 125 numbers

Test #5:

score: 0
Accepted
time: 1664ms
memory: 4392kb

input:

5
-4 -1 4 2.566 3.253
1 -1 2 3.826 4.000
1 2 5 4.113 3.814
-1 -4 2 4.386 3.959
-1 -2 1 5.785 3.937
5
4 2 4 2.417 0.945
-5 -3 3 4.946 5.172
2 -2 2 2.380 0.205
3 3 4 0.766 4.402
-2 4 5 3.442 4.263
5
0 -4 3 5.172 0.603
-4 -5 3 1.321 3.688
-5 1 4 4.363 3.784
-5 -1 4 2.943 2.791
-2 5 3 5.292 5.765
5
-5 -...

output:

79.693582239334077
91.736881246842103
79.436470640508460
77.453235871714085
98.285983681175608
71.089216970334988
7.725498403134583
103.276613145004944
18.876110626753857
83.851723310187722
37.132095376387312
80.144202170853561
100.607512086478422
89.227845251574834
94.924727000219860
24.35599455869...

result:

ok 100 numbers

Test #6:

score: 0
Accepted
time: 1959ms
memory: 4400kb

input:

10
4 4 4 2.043 4.661
0 -2 3 4.728 5.010
1 5 5 0.478 2.500
1 2 4 3.314 2.904
4 -4 5 3.408 5.869
-3 1 5 0.644 2.968
2 0 4 5.532 0.421
2 -3 1 3.492 0.855
-3 -3 5 4.475 4.896
-4 -1 3 0.873 1.815
10
-2 -1 3 4.786 3.714
-4 -3 1 0.155 4.804
-1 -5 3 4.225 2.500
-4 -1 4 5.536 3.954
4 -2 4 5.516 2.204
-3 2 4 ...

output:

217.462248317452264
137.080440109820302
68.280445191359604
81.674908607647581
161.394724771617149
109.854751276345993
88.851096691069245
149.663822629827763
141.260464727184683
150.828575451893215
103.530626315654771
80.042098015938137
135.587229682717094
124.154662928690826
142.296814806591044
136....

result:

ok 50 numbers

Test #7:

score: -100
Time Limit Exceeded

input:

9
6 -5 6 4.848 5.374
9 4 3 2.135 4.598
8 -4 6 4.443 5.157
0 5 9 3.605 1.226
7 -4 9 1.917 4.657
6 -7 8 3.621 0.258
3 3 4 1.955 5.563
-6 -5 5 3.174 3.778
-10 9 1 5.808 1.214
10
2 0 8 5.479 1.980
-3 -1 10 2.909 0.574
-8 -10 4 1.758 4.039
2 -6 9 5.761 4.499
1 1 2 0.115 0.897
-3 7 6 0.574 4.703
-4 5 6 0....

output:


result: