QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #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
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';
}*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4172kb
input:
100 45 90 0 -20 0.1
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 0ms
memory: 4068kb
input:
100 45 90 0 -20 .999
output:
14
result:
ok single line: '14'
Test #3:
score: 0
Accepted
time: 0ms
memory: 4160kb
input:
3 1 1 2 -2 .9
output:
12
result:
ok single line: '12'
Test #4:
score: 0
Accepted
time: 0ms
memory: 4248kb
input:
3 5 5 -1 1 .9
output:
3
result:
ok single line: '3'
Test #5:
score: 0
Accepted
time: 0ms
memory: 4172kb
input:
10 1 1 0 0 .9
output:
60
result:
ok single line: '60'
Test #6:
score: 0
Accepted
time: 0ms
memory: 4060kb
input:
1 1 1 -10000 -10000 .5
output:
0
result:
ok single line: '0'
Test #7:
score: 0
Accepted
time: 602ms
memory: 36668kb
input:
1000 1 1 -10000 10000 .9
output:
6412
result:
ok single line: '6412'
Test #8:
score: 0
Accepted
time: 0ms
memory: 4256kb
input:
1000 3000 3000 -10000 10000 .9
output:
0
result:
ok single line: '0'
Test #9:
score: 0
Accepted
time: 0ms
memory: 4252kb
input:
5 2 10 -6 -5 .22
output:
2
result:
ok single line: '2'
Test #10:
score: 0
Accepted
time: 0ms
memory: 4252kb
input:
5 2 10 -6 -5 .20
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 0ms
memory: 4056kb
input:
5 9 10 -5 -6 .05
output:
0
result:
ok single line: '0'
Test #12:
score: 0
Accepted
time: 0ms
memory: 4128kb
input:
5 9 10 -5 -6 .07
output:
2
result:
ok single line: '2'
Test #13:
score: 0
Accepted
time: 0ms
memory: 4244kb
input:
5 8 8 -4 -4 .07
output:
4
result:
ok single line: '4'
Test #14:
score: 0
Accepted
time: 0ms
memory: 4100kb
input:
5 8 8 -4 -4 .06
output:
0
result:
ok single line: '0'
Test #15:
score: 0
Accepted
time: 0ms
memory: 4076kb
input:
10 15 15 -1 1 .58
output:
0
result:
ok single line: '0'
Test #16:
score: 0
Accepted
time: 0ms
memory: 4268kb
input:
10 15 15 -1 1 .60
output:
1
result:
ok single line: '1'
Test #17:
score: 0
Accepted
time: 0ms
memory: 4124kb
input:
5 4 2 -10 -1 .23
output:
0
result:
ok single line: '0'
Test #18:
score: 0
Accepted
time: 0ms
memory: 4160kb
input:
5 4 2 -10 -1 .24
output:
4
result:
ok single line: '4'
Test #19:
score: 0
Accepted
time: 0ms
memory: 4264kb
input:
25 2 5 6825 1407 0.341
output:
28
result:
ok single line: '28'
Test #20:
score: 0
Accepted
time: 0ms
memory: 4128kb
input:
21 3 5 8580 -2814 0.041
output:
2
result:
ok single line: '2'
Test #21:
score: 0
Accepted
time: 0ms
memory: 4104kb
input:
47 8 3 992 -4517 0.364
output:
26
result:
ok single line: '26'
Test #22:
score: 0
Accepted
time: 0ms
memory: 4108kb
input:
45 6 9 -3799 9831 0.683
output:
35
result:
ok single line: '35'
Test #23:
score: 0
Accepted
time: 1ms
memory: 4260kb
input:
36 1 8 -876 3329 0.699
output:
118
result:
ok single line: '118'
Test #24:
score: 0
Accepted
time: 0ms
memory: 4080kb
input:
29 1028 2688 8607 -2666 0.261
output:
1
result:
ok single line: '1'
Test #25:
score: 0
Accepted
time: 0ms
memory: 4152kb
input:
38 2942 2253 -3028 -7432 0.912
output:
0
result:
ok single line: '0'
Test #26:
score: 0
Accepted
time: 0ms
memory: 4128kb
input:
21 1675 2566 -2332 9816 0.999
output:
0
result:
ok single line: '0'
Test #27:
score: 0
Accepted
time: 0ms
memory: 4316kb
input:
32 2948 2907 6845 -1952 0.176
output:
0
result:
ok single line: '0'
Test #28:
score: 0
Accepted
time: 0ms
memory: 4096kb
input:
41 1635 2831 695 1466 0.058
output:
0
result:
ok single line: '0'
Test #29:
score: 0
Accepted
time: 15ms
memory: 4648kb
input:
908 5 7 505 1873 0.42
output:
578
result:
ok single line: '578'
Test #30:
score: 0
Accepted
time: 5ms
memory: 4380kb
input:
681 7 9 1889 598 0.627
output:
409
result:
ok single line: '409'
Test #31:
score: 0
Accepted
time: 9ms
memory: 4284kb
input:
513 9 2 6644 -468 0.022
output:
84
result:
ok single line: '84'
Test #32:
score: 0
Accepted
time: 16ms
memory: 4708kb
input:
667 3 6 662 -1479 0.498
output:
640
result:
ok single line: '640'
Test #33:
score: 0
Accepted
time: 13ms
memory: 4712kb
input:
647 5 4 7821 -316 0.786
output:
826
result:
ok single line: '826'
Test #34:
score: 0
Accepted
time: 0ms
memory: 4056kb
input:
924 1627 2356 1249 -6098 0.049
output:
0
result:
ok single line: '0'
Test #35:
score: 0
Accepted
time: 0ms
memory: 4128kb
input:
876 2985 1113 7094 9995 0.801
output:
0
result:
ok single line: '0'
Test #36:
score: 0
Accepted
time: 0ms
memory: 4060kb
input:
738 2209 2397 -3532 356 0.556
output:
1
result:
ok single line: '1'
Test #37:
score: 0
Accepted
time: 0ms
memory: 4172kb
input:
677 1474 1634 3334 4944 0.271
output:
2
result:
ok single line: '2'
Test #38:
score: 0
Accepted
time: 0ms
memory: 4316kb
input:
518 2083 2687 1293 -5938 0.265
output:
0
result:
ok single line: '0'