QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#632221 | #513. Pizza Cutting | chuchu | TL | 3ms | 4224kb | C++20 | 3.8kb | 2024-10-12 13:00:23 | 2024-10-12 13:00:23 |
Judging History
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.y < r) c.y += dy;
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";
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 4040kb
input:
100 45 90 0 -20 0.1
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 0ms
memory: 4180kb
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: 4116kb
input:
3 5 5 -1 1 .9
output:
3
result:
ok single line: '3'
Test #5:
score: 0
Accepted
time: 0ms
memory: 4148kb
input:
10 1 1 0 0 .9
output:
60
result:
ok single line: '60'
Test #6:
score: 0
Accepted
time: 3ms
memory: 4224kb
input:
1 1 1 -10000 -10000 .5
output:
0
result:
ok single line: '0'
Test #7:
score: -100
Time Limit Exceeded
input:
1000 1 1 -10000 10000 .9