QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#723351	#513. Pizza Cutting	TheZone	AC ✓	602ms	36668kb	C++20	6.5kb	2024-11-07 21:55:11	2024-11-07 21:55:11

Judging History

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

[2024-11-07 21:55:11]
评测

测评结果：AC
用时：602ms
内存：36668kb

查看

[2024-11-07 21:55:11]
提交

answer

#include <bits/stdc++.h>
using namespace std;

#define rep(i,a,b) for (int i=a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;


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;}
    double dist() const { return sqrt((double)dist2()); }
    double angle() const { return atan2(y,x);}
    P unit() const { return *this/dist(); }
    P perp() const { return P(-y,x); }
    P normal() const { return perp().unit(); }
    P rotate(double 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<double> P;
#define arg(p, q) atan2(p.cross(q), p.dot(q))
double circlePoly(P c, double r, vector<P> ps) {
    auto tri = [&](P p, P q) {
        auto r2 = r*r/2;
        P d = q-p;
        auto a  = d.dot(p)/d.dist2(), b = (p.dist2()-r*r)/d.dist2();
        auto det = a*a-b;
        if (det <= 0) return arg(p,q)*r2;
        auto s = max(0., -a-sqrt(det)), t = min(1., -a+sqrt(det));
        if (t < 0 || 1 <= s) return arg(p, q) * r2;
        P u = p+d*s, v=p+d*t;
        return arg(p,u) * r2 + u.cross(v)/2 + arg(v,q)*r2;
    };
    auto sum = 0.0;
    rep(i,0,sz(ps))
        sum += tri(ps[i] - c, ps[(i+1)%sz(ps)] - c);
    return sum;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    int DX, DY, X, Y;
    double R, PR;
    cin >>R >> DX >> DY >> X >> Y >> PR;

    while (X < R) X += DX;
    while (X >= R) X -= DX;
    while (Y < R) Y += DY;
    while (Y >= R) Y -= DY;

    double dx = DX;
    double dy = DY;
    P orig{0,0};
    auto eval_square = [&](double cx, double cy) -> double {
       // cout << cx << ' ' << cy << '\n';
        vector<P> ps;
        ps.push_back(P{cx,cy});
        ps.push_back(P{cx+dx,cy});
        ps.push_back(P{cx+dx,cy+dy});
        ps.push_back(P{cx,cy+dy});
        double a = circlePoly(orig, R, ps);
        return a;
    };

    vector<double> areas;

    int cx = X, cy = Y;
    while (true) {
        while (true) {
            // eval square
            double  a = eval_square(cx, cy);
            if (a > 1e-9) areas.push_back(a);
            if (cx < -R) break;
            cx -= DX;
        }
        if (cy < -R) break;
        cy -= DY;
        cx = X;
    }
    sort(areas.begin(), areas.end());

    int ans = 0;
    int N = areas.size()-1;
    const double EPS = 1e-6;
    double yy = areas.back();
    for (int i = 0; i < N; ++i) {
        double xx = areas[i];
        if (xx/yy <= PR + EPS) ++ans;
    }
    cout << ans << '\n';

}/*#include <bits/stdc++.h>
using namespace std;

#define rep(i,a,b) for (int i=a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;


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;}
    double dist() const { return sqrt((double)dist2()); }
    double angle() const { return atan2(y,x);}
    P unit() const { return *this/dist(); }
    P perp() const { return P(-y,x); }
    P normal() const { return perp().unit(); }
    P rotate(double 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<double> P;
#define arg(p, q) atan2(p.cross(q), p.dot(q))
double circlePoly(P c, double r, vector<P> ps) {
    auto tri = [&](P p, P q) {
        auto r2 = r*r/2;
        P d = q-p;
        auto a  = d.dot(p)/d.dist2(), b = (p.dist2()-r*r)/d.dist2();
        auto det = a*a-b;
        if (det <= 0) return arg(p,q)*r2;
        auto s = max(0., -a-sqrt(det)), t = min(1., -a+sqrt(det));
        if (t < 0 || 1 <= s) return arg(p, q) * r2;
        P u = p+d*s, v=p+d*t;
        return arg(p,u) * r2 + u.cross(v)/2 + arg(v,q)*r2;
    };
    auto sum = 0.0;
    rep(i,0,sz(ps))
        sum += tri(ps[i] - c, ps[(i+1)%sz(ps)] - c);
    return sum;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    int DX, DY, X, Y;
    double R, PR;
    cin >>R >> DX >> DY >> X >> Y >> PR;

    while (X < R) X += DX;
    while (X >= R) X -= DX;
    while (Y < R) Y += DY;
    while (Y >= R) Y -= DY;

    double dx = DX;
    double dy = DY;
    P orig{0,0};
    auto eval_square = [&](double cx, double cy) -> double {
       // cout << cx << ' ' << cy << '\n';
        vector<P> ps;
        ps.push_back(P{cx,cy});
        ps.push_back(P{cx+dx,cy});
        ps.push_back(P{cx+dx,cy+dy});
        ps.push_back(P{cx,cy+dy});
        double a = circlePoly(orig, R, ps);
        return a;
    };

    vector<double> areas;

    int cx = X, cy = Y;
    while (true) {
        while (true) {
            // eval square
            double  a = eval_square(cx, cy);
            if (a > 1e-9) areas.push_back(a);
            if (cx < -R) break;
            cx -= DX;
        }
        if (cy < -R) break;
        cy -= DY;
    for (int i = 0; i < N; ++i) {
        double xx = areas[i];
        if (xx/yy <= PR + EPS) ++ans;
    }
    cout << ans << '\n';

}*/

源文件, 语言: C++20

详细

Test #1:

score: 100

Accepted

time: 0ms

memory: 4172kb

input:

100 45 90 0 -20 0.1

output:

result:

ok single line: '4'

Test #2:

score: 0

Accepted

time: 0ms

memory: 4068kb

input:

100 45 90 0 -20 .999

output:

result:

ok single line: '14'

Test #3:

score: 0

Accepted

time: 0ms

memory: 4160kb

input:

3 1 1 2 -2 .9

output:

result:

ok single line: '12'

Test #4:

score: 0

Accepted

time: 0ms

memory: 4248kb

input:

3 5 5 -1 1 .9

output:

result:

ok single line: '3'

Test #5:

score: 0

Accepted

time: 0ms

memory: 4172kb

input:

10 1 1 0 0 .9

output:

result:

ok single line: '60'

Test #6:

score: 0

Accepted

time: 0ms

memory: 4060kb

input:

1 1 1 -10000 -10000 .5

output:

result:

ok single line: '0'

Test #7:

score: 0

Accepted

time: 602ms

memory: 36668kb

input:

1000 1 1 -10000 10000 .9

output:

result:

ok single line: '6412'

Test #8:

score: 0

Accepted

time: 0ms

memory: 4256kb

input:

1000 3000 3000 -10000 10000 .9

output:

result:

ok single line: '0'

Test #9:

score: 0

Accepted

time: 0ms

memory: 4252kb

input:

5 2 10 -6 -5 .22

output:

result:

ok single line: '2'

Test #10:

score: 0

Accepted

time: 0ms

memory: 4252kb

input:

5 2 10 -6 -5 .20

output:

result:

ok single line: '0'

Test #11:

score: 0

Accepted

time: 0ms

memory: 4056kb

input:

5 9 10 -5 -6 .05

output:

result:

ok single line: '0'

Test #12:

score: 0

Accepted

time: 0ms

memory: 4128kb

input:

5 9 10 -5 -6 .07

output:

result:

ok single line: '2'

Test #13:

score: 0

Accepted

time: 0ms

memory: 4244kb

input:

5 8 8 -4 -4 .07

output:

result:

ok single line: '4'

Test #14:

score: 0

Accepted

time: 0ms

memory: 4100kb

input:

5 8 8 -4 -4 .06

output:

result:

ok single line: '0'

Test #15:

score: 0

Accepted

time: 0ms

memory: 4076kb

input:

10 15 15 -1 1 .58

output:

result:

ok single line: '0'

Test #16:

score: 0

Accepted

time: 0ms

memory: 4268kb

input:

10 15 15 -1 1 .60

output:

result:

ok single line: '1'

Test #17:

score: 0

Accepted

time: 0ms

memory: 4124kb

input:

5 4 2 -10 -1 .23

output:

result:

ok single line: '0'

Test #18:

score: 0

Accepted

time: 0ms

memory: 4160kb

input:

5 4 2 -10 -1 .24

output:

result:

ok single line: '4'

Test #19:

score: 0

Accepted

time: 0ms

memory: 4264kb

input:

25 2 5 6825 1407 0.341

output:

result:

ok single line: '28'

Test #20:

score: 0

Accepted

time: 0ms

memory: 4128kb

input:

21 3 5 8580 -2814 0.041

output:

result:

ok single line: '2'

Test #21:

score: 0

Accepted

time: 0ms

memory: 4104kb

input:

47 8 3 992 -4517 0.364

output:

result:

ok single line: '26'

Test #22:

score: 0

Accepted

time: 0ms

memory: 4108kb

input:

45 6 9 -3799 9831 0.683

output:

result:

ok single line: '35'

Test #23:

score: 0

Accepted

time: 1ms

memory: 4260kb

input:

36 1 8 -876 3329 0.699

output:

result:

ok single line: '118'

Test #24:

score: 0

Accepted

time: 0ms

memory: 4080kb

input:

29 1028 2688 8607 -2666 0.261

output:

result:

ok single line: '1'

Test #25:

score: 0

Accepted

time: 0ms

memory: 4152kb

input:

38 2942 2253 -3028 -7432 0.912

output:

result:

ok single line: '0'

Test #26:

score: 0

Accepted

time: 0ms

memory: 4128kb

input:

21 1675 2566 -2332 9816 0.999

output:

result:

ok single line: '0'

Test #27:

score: 0

Accepted

time: 0ms

memory: 4316kb

input:

32 2948 2907 6845 -1952 0.176

output:

result:

ok single line: '0'

Test #28:

score: 0

Accepted

time: 0ms

memory: 4096kb

input:

41 1635 2831 695 1466 0.058

output:

result:

ok single line: '0'

Test #29:

score: 0

Accepted

time: 15ms

memory: 4648kb

input:

908 5 7 505 1873 0.42

output:

result:

ok single line: '578'

Test #30:

score: 0

Accepted

time: 5ms

memory: 4380kb

input:

681 7 9 1889 598 0.627

output:

result:

ok single line: '409'

Test #31:

score: 0

Accepted

time: 9ms

memory: 4284kb

input:

513 9 2 6644 -468 0.022

output:

result:

ok single line: '84'

Test #32:

score: 0

Accepted

time: 16ms

memory: 4708kb

input:

667 3 6 662 -1479 0.498

output:

result:

ok single line: '640'

Test #33:

score: 0

Accepted

time: 13ms

memory: 4712kb

input:

647 5 4 7821 -316 0.786

output:

result:

ok single line: '826'

Test #34:

score: 0

Accepted

time: 0ms

memory: 4056kb

input:

924 1627 2356 1249 -6098 0.049

output:

result:

ok single line: '0'

Test #35:

score: 0

Accepted

time: 0ms

memory: 4128kb

input:

876 2985 1113 7094 9995 0.801

output:

result:

ok single line: '0'

Test #36:

score: 0

Accepted

time: 0ms

memory: 4060kb

input:

738 2209 2397 -3532 356 0.556

output:

result:

ok single line: '1'

Test #37:

score: 0

Accepted

time: 0ms

memory: 4172kb

input:

677 1474 1634 3334 4944 0.271

output:

result:

ok single line: '2'

Test #38:

score: 0

Accepted

time: 0ms

memory: 4316kb

input:

518 2083 2687 1293 -5938 0.265

output:

result:

ok single line: '0'