QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#632232#513. Pizza CuttingchuchuAC ✓103ms4312kbC++204.0kb2024-10-12 13:04:402024-10-12 13:04:41

Judging History

This is the latest submission verdict.

  • [2024-10-12 13:04:41]
  • Judged
  • Verdict: AC
  • Time: 103ms
  • Memory: 4312kb
  • [2024-10-12 13:04:40]
  • Submitted

answer

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

#pragma GCC optimize("O3")

#define rep(i,a,b) for (int i = a; i < b; ++i)
#define sz(s) ((int)(s).size())

typedef float ld;
// #define double float

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()); }
	// angle to x-axis in interval [-pi, pi]
	double 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(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) {
    // cerr << "enter" << endl;
	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.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;
}

ld eps = 1e-6;

int main() {
    ld r, dx, dy, x, y, p; cin >> r >> dx >> dy >> x >> y >> p;
    P c{x, y};
    while (c.x < -r) c.x += dx;
    while (c.x > -r) c.x -= dx;
    while (c.y > r) c.y -= dy;
    while (c.y < r) c.y += dy;
    // cerr << "owo" << endl;
    // cerr << c.x << " " << c.y << endl;


    ld big = 0.0, small = 1e9;

    vector<ld> pcs;

    auto dist = [&] (auto x, auto y) {
        return x*x+y*y;
    };

    auto inside = [&] (auto x, auto y) {
        return dist(c.x+dx, c.y) < r*r &&
            dist(c.x, c.y) < r*r &&
            dist(c.x, c.y-dy) < r*r &&
            dist(c.x+dx, c.y-dy) < r*r;
    };

    ld tx = c.x;
    int skip = 0;
    while (c.y > -r) {
        while (c.x < r) {
            if (inside(c.x, c.y)) {
                if (skip) {
                    for (int i = 1<<20; i > 0; i >>= 1) {
                        c.x += dx * i;
                        if (dist(c.x+dx, c.y-(c.y<0?dy:0)) > r*r) c.x -= dx * i;
                    }
                    c.x += dx;
                    continue;
                }
                skip = 1;
            }
            vector<P> poly;
            poly.push_back(P{c.x+dx, c.y});
            poly.push_back(P{c.x, c.y});
            poly.push_back(P{c.x, c.y-dy});
            poly.push_back(P{c.x+dx, c.y-dy});

            ld area = circlePoly(P{0, 0}, r, poly);
            // cerr << area << endl;

            c.x += dx;
            if (area < eps) continue;
            big = max(big, area);
            pcs.push_back(area);

            // cerr << c.x << endl;
        }

        c.y -= dy;
        c.x = tx;
        // skip ++;
            // cerr << "test" << endl;

    }

    // cerr << big << endl;

    int ans = 0;
    for (auto x : pcs) {
        // cerr << x << endl;
        if (x/big-p < eps) ans++;
    }
    cout << ans << "\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 4044kb

input:

100 45 90 0 -20 0.1

output:

4

result:

ok single line: '4'

Test #2:

score: 0
Accepted
time: 0ms
memory: 4236kb

input:

100 45 90 0 -20 .999

output:

14

result:

ok single line: '14'

Test #3:

score: 0
Accepted
time: 0ms
memory: 4244kb

input:

3 1 1 2 -2 .9

output:

12

result:

ok single line: '12'

Test #4:

score: 0
Accepted
time: 0ms
memory: 4156kb

input:

3 5 5 -1 1 .9

output:

3

result:

ok single line: '3'

Test #5:

score: 0
Accepted
time: 0ms
memory: 4232kb

input:

10 1 1 0 0 .9

output:

60

result:

ok single line: '60'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3988kb

input:

1 1 1 -10000 -10000 .5

output:

0

result:

ok single line: '0'

Test #7:

score: 0
Accepted
time: 103ms
memory: 4156kb

input:

1000 1 1 -10000 10000 .9

output:

6412

result:

ok single line: '6412'

Test #8:

score: 0
Accepted
time: 0ms
memory: 4056kb

input:

1000 3000 3000 -10000 10000 .9

output:

0

result:

ok single line: '0'

Test #9:

score: 0
Accepted
time: 0ms
memory: 4116kb

input:

5 2 10 -6 -5 .22

output:

2

result:

ok single line: '2'

Test #10:

score: 0
Accepted
time: 0ms
memory: 4196kb

input:

5 2 10 -6 -5 .20

output:

0

result:

ok single line: '0'

Test #11:

score: 0
Accepted
time: 0ms
memory: 4176kb

input:

5 9 10 -5 -6 .05

output:

0

result:

ok single line: '0'

Test #12:

score: 0
Accepted
time: 0ms
memory: 4236kb

input:

5 9 10 -5 -6 .07

output:

2

result:

ok single line: '2'

Test #13:

score: 0
Accepted
time: 0ms
memory: 4176kb

input:

5 8 8 -4 -4 .07

output:

4

result:

ok single line: '4'

Test #14:

score: 0
Accepted
time: 0ms
memory: 4116kb

input:

5 8 8 -4 -4 .06

output:

0

result:

ok single line: '0'

Test #15:

score: 0
Accepted
time: 0ms
memory: 4084kb

input:

10 15 15 -1 1 .58

output:

0

result:

ok single line: '0'

Test #16:

score: 0
Accepted
time: 0ms
memory: 4124kb

input:

10 15 15 -1 1 .60

output:

1

result:

ok single line: '1'

Test #17:

score: 0
Accepted
time: 0ms
memory: 4308kb

input:

5 4 2 -10 -1 .23

output:

0

result:

ok single line: '0'

Test #18:

score: 0
Accepted
time: 0ms
memory: 4132kb

input:

5 4 2 -10 -1 .24

output:

4

result:

ok single line: '4'

Test #19:

score: 0
Accepted
time: 0ms
memory: 4312kb

input:

25 2 5 6825 1407 0.341

output:

28

result:

ok single line: '28'

Test #20:

score: 0
Accepted
time: 0ms
memory: 4228kb

input:

21 3 5 8580 -2814 0.041

output:

2

result:

ok single line: '2'

Test #21:

score: 0
Accepted
time: 0ms
memory: 4312kb

input:

47 8 3 992 -4517 0.364

output:

26

result:

ok single line: '26'

Test #22:

score: 0
Accepted
time: 0ms
memory: 4308kb

input:

45 6 9 -3799 9831 0.683

output:

35

result:

ok single line: '35'

Test #23:

score: 0
Accepted
time: 0ms
memory: 4088kb

input:

36 1 8 -876 3329 0.699

output:

118

result:

ok single line: '118'

Test #24:

score: 0
Accepted
time: 0ms
memory: 4052kb

input:

29 1028 2688 8607 -2666 0.261

output:

1

result:

ok single line: '1'

Test #25:

score: 0
Accepted
time: 0ms
memory: 4228kb

input:

38 2942 2253 -3028 -7432 0.912

output:

0

result:

ok single line: '0'

Test #26:

score: 0
Accepted
time: 0ms
memory: 4116kb

input:

21 1675 2566 -2332 9816 0.999

output:

0

result:

ok single line: '0'

Test #27:

score: 0
Accepted
time: 0ms
memory: 4044kb

input:

32 2948 2907 6845 -1952 0.176

output:

0

result:

ok single line: '0'

Test #28:

score: 0
Accepted
time: 0ms
memory: 4260kb

input:

41 1635 2831 695 1466 0.058

output:

0

result:

ok single line: '0'

Test #29:

score: 0
Accepted
time: 3ms
memory: 4092kb

input:

908 5 7 505 1873 0.42

output:

578

result:

ok single line: '578'

Test #30:

score: 0
Accepted
time: 1ms
memory: 4092kb

input:

681 7 9 1889 598 0.627

output:

409

result:

ok single line: '409'

Test #31:

score: 0
Accepted
time: 2ms
memory: 4132kb

input:

513 9 2 6644 -468 0.022

output:

84

result:

ok single line: '84'

Test #32:

score: 0
Accepted
time: 0ms
memory: 4108kb

input:

667 3 6 662 -1479 0.498

output:

640

result:

ok single line: '640'

Test #33:

score: 0
Accepted
time: 3ms
memory: 4096kb

input:

647 5 4 7821 -316 0.786

output:

826

result:

ok single line: '826'

Test #34:

score: 0
Accepted
time: 0ms
memory: 4156kb

input:

924 1627 2356 1249 -6098 0.049

output:

0

result:

ok single line: '0'

Test #35:

score: 0
Accepted
time: 0ms
memory: 4088kb

input:

876 2985 1113 7094 9995 0.801

output:

0

result:

ok single line: '0'

Test #36:

score: 0
Accepted
time: 0ms
memory: 4184kb

input:

738 2209 2397 -3532 356 0.556

output:

1

result:

ok single line: '1'

Test #37:

score: 0
Accepted
time: 0ms
memory: 4260kb

input:

677 1474 1634 3334 4944 0.271

output:

2

result:

ok single line: '2'

Test #38:

score: 0
Accepted
time: 0ms
memory: 4092kb

input:

518 2083 2687 1293 -5938 0.265

output:

0

result:

ok single line: '0'