QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#731003 | #9576. Ordainer of Inexorable Judgment | ucup-team2796# | WA | 0ms | 4068kb | C++17 | 18.3kb | 2024-11-09 23:05:14 | 2024-11-09 23:05:15 |
Judging History
你现在查看的是最新测评结果
- [2024-12-23 14:23:26]
- hack成功,自动添加数据
- (/hack/1303)
- [2024-12-06 11:32:56]
- hack成功,自动添加数据
- (/hack/1271)
- [2024-11-14 21:58:28]
- hack成功,自动添加数据
- (/hack/1181)
- [2024-11-09 23:05:14]
- 提交
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rrep(i, a, b) for (int i = (int)(b)-1; i >= (int)(a); i--)
#define ALL(v) (v).begin(), (v).end()
#define UNIQUE(v) sort(ALL(v)), (v).erase(unique(ALL(v)), (v).end())
#define SZ(v) (int)v.size()
#define MIN(v) *min_element(ALL(v))
#define MAX(v) *max_element(ALL(v))
#define LB(v, x) int(lower_bound(ALL(v), (x)) - (v).begin())
#define UB(v, x) int(upper_bound(ALL(v), (x)) - (v).begin())
using uint = unsigned int;
using ll = long long int;
using ull = unsigned long long;
using i128 = __int128_t;
using u128 = __uint128_t;
const int inf = 0x3fffffff;
const ll INF = 0x1fffffffffffffff;
template <typename T> inline bool chmax(T &a, T b) {
if (a < b) {
a = b;
return 1;
}
return 0;
}
template <typename T> inline bool chmin(T &a, T b) {
if (a > b) {
a = b;
return 1;
}
return 0;
}
template <typename T, typename U> T ceil(T x, U y) {
assert(y != 0);
if (y < 0)
x = -x, y = -y;
return (x > 0 ? (x + y - 1) / y : x / y);
}
template <typename T, typename U> T floor(T x, U y) {
assert(y != 0);
if (y < 0)
x = -x, y = -y;
return (x > 0 ? x / y : (x - y + 1) / y);
}
template <typename T> int popcnt(T x) {
return __builtin_popcountll(x);
}
template <typename T> int topbit(T x) {
return (x == 0 ? -1 : 63 - __builtin_clzll(x));
}
template <typename T> int lowbit(T x) {
return (x == 0 ? -1 : __builtin_ctzll(x));
}
template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
os << "P(" << p.first << ", " << p.second << ")";
return os;
}
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) {
os << "{";
for (int i = 0; i < vec.size(); i++) {
os << vec[i] << (i + 1 == vec.size() ? "" : ", ");
}
os << "}";
return os;
}
template <typename T, typename U>
ostream &operator<<(ostream &os, const map<T, U> &map_var) {
os << "{";
for (auto itr = map_var.begin(); itr != map_var.end(); itr++) {
os << "(" << itr->first << ", " << itr->second << ")";
itr++;
if (itr != map_var.end())
os << ", ";
itr--;
}
os << "}";
return os;
}
template <typename T> ostream &operator<<(ostream &os, const set<T> &set_var) {
os << "{";
for (auto itr = set_var.begin(); itr != set_var.end(); itr++) {
os << *itr;
++itr;
if (itr != set_var.end())
os << ", ";
itr--;
}
os << "}";
return os;
}
#ifdef LOCAL
#define show(...) _show(0, #__VA_ARGS__, __VA_ARGS__)
#else
#define show(...) true
#endif
template <typename T> void _show(int i, T name) {
cerr << '\n';
}
template <typename T1, typename T2, typename... T3>
void _show(int i, const T1 &a, const T2 &b, const T3 &...c) {
for (; a[i] != ',' && a[i] != '\0'; i++)
cerr << a[i];
cerr << ":" << b << " ";
_show(i + 1, a, c...);
}
/**
* @brief template
*/
using T = long double;
const T eps = 1e-12;
using Point = complex<T>;
using Poly = vector<Point>;
#define X real()
#define Y imag()
template <typename T> inline bool eq(const T &a, const T &b) {
return fabs(a - b) < eps;
}
bool cmp(const Point &a, const Point &b) {
auto sub = [&](Point a) {
return (a.Y < 0 ? -1 : (a.Y == 0 && a.X >= 0 ? 0 : 1));
};
if (sub(a) != sub(b))
return sub(a) < sub(b);
return a.Y * b.X < a.X * b.Y;
}
struct Line {
Point a, b, dir;
Line() {}
Line(Point _a, Point _b) : a(_a), b(_b), dir(b - a) {}
Line(T A, T B, T C) {
if (eq(A, (T).0)) {
a = Point(0, C / B), b = Point(1 / C / B);
} else if (eq(B, (T).0)) {
a = Point(C / A, 0), b = Point(C / A, 1);
} else {
a = Point(0, C / B), b = Point(C / A, 0);
}
}
};
struct Segment : Line {
Segment() {}
Segment(Point _a, Point _b) : Line(_a, _b) {}
};
struct Circle {
Point p;
T r;
Circle() {}
Circle(Point _p, T _r) : p(_p), r(_r) {}
};
istream &operator>>(istream &is, Point &p) {
T x, y;
is >> x >> y;
p = Point(x, y);
return is;
}
ostream &operator<<(ostream &os, Point &p) {
os << fixed << setprecision(12) << p.X << ' ' << p.Y;
return os;
}
Point unit(const Point &a) {
return a / abs(a);
}
T dot(const Point &a, const Point &b) {
return a.X * b.X + a.Y * b.Y;
}
T cross(const Point &a, const Point &b) {
return a.X * b.Y - a.Y * b.X;
}
Point rot(const Point &a, const T &theta) {
return Point(cos(theta) * a.X - sin(theta) * a.Y,
sin(theta) * a.X + cos(theta) * a.Y);
}
Point rot90(const Point &a) {
return Point(-a.Y, a.X);
}
T arg(const Point &a, const Point &b, const Point &c) {
double ret = acos(dot(a - b, c - b) / abs(a - b) / abs(c - b));
if (cross(a - b, c - b) < 0)
ret = -ret;
return ret;
}
Point Projection(const Line &l, const Point &p) {
T t = dot(p - l.a, l.a - l.b) / norm(l.a - l.b);
return l.a + (l.a - l.b) * t;
}
Point Projection(const Segment &l, const Point &p) {
T t = dot(p - l.a, l.a - l.b) / norm(l.a - l.b);
return l.a + (l.a - l.b) * t;
}
Point Reflection(const Line &l, const Point &p) {
return p + (Projection(l, p) - p) * (T)2.;
}
int ccw(const Point &a, Point b, Point c) {
b -= a;
c -= a;
if (cross(b, c) > eps)
return 1; // ccw
if (cross(b, c) < -eps)
return -1; // cw
if (dot(b, c) < 0)
return 2; // c,a,b
if (norm(b) < norm(c))
return -2; // a,b,c
return 0; // a,c,b
}
bool isOrthogonal(const Line &a, const Line &b) {
return eq(dot(a.b - a.a, b.b - b.a), (T).0);
}
bool isParallel(const Line &a, const Line &b) {
return eq(cross(a.b - a.a, b.b - b.a), (T).0);
}
bool isIntersect(const Segment &a, const Segment &b) {
return ccw(a.a, a.b, b.a) * ccw(a.a, a.b, b.b) <= 0 and
ccw(b.a, b.b, a.a) * ccw(b.a, b.b, a.b) <= 0;
}
int isIntersect(const Circle &a, const Circle &b) {
T d = abs(a.p - b.p);
if (d > a.r + b.r + eps)
return 4;
if (eq(d, a.r + b.r))
return 3;
if (eq(d, abs(a.r - b.r)))
return 1;
if (d < abs(a.r - b.r) - eps)
return 0;
return 2;
}
T Dist(const Line &a, const Point &b) {
Point c = Projection(a, b);
return abs(c - b);
}
T Dist(const Segment &a, const Point &b) {
if (dot(a.b - a.a, b - a.a) < eps)
return abs(b - a.a);
if (dot(a.a - a.b, b - a.b) < eps)
return abs(b - a.b);
return abs(cross(a.b - a.a, b - a.a)) / abs(a.b - a.a);
}
T Dist(const Segment &a, const Segment &b) {
if (isIntersect(a, b))
return (T).0;
T res = min({Dist(a, b.a), Dist(a, b.b), Dist(b, a.a), Dist(b, a.b)});
return res;
}
Point Intersection(const Line &a, const Line &b) {
T d1 = cross(a.b - a.a, b.b - b.a);
T d2 = cross(a.b - a.a, a.b - b.a);
if (eq(d1, (T)0.) and eq(d2, (T)0.))
return b.a;
return b.a + (b.b - b.a) * (d2 / d1);
}
Poly Intersection(const Circle &a, const Line &b) {
Poly res;
T d = Dist(b, a.p);
if (d > a.r + eps)
return res;
Point h = Projection(b, a.p);
if (eq(d, a.r)) {
res.push_back(h);
return res;
}
Point e = unit(b.b - b.a);
T ph = sqrt(a.r * a.r - d * d);
res.push_back(h - e * ph);
res.push_back(h + e * ph);
return res;
}
Poly Intersection(const Circle &a, const Segment &b) {
Line c(b.a, b.b);
Poly sub = Intersection(a, c);
double xmi = min(b.a.X, b.b.X), xma = max(b.a.X, b.b.X);
double ymi = min(b.a.Y, b.b.Y), yma = max(b.a.Y, b.b.Y);
Poly res;
rep(i, 0, sub.size()) {
if (xmi <= sub[i].X + eps and sub[i].X - eps <= xma and
ymi <= sub[i].Y + eps and sub[i].Y - eps <= yma) {
res.push_back(sub[i]);
}
}
return res;
}
Poly Intersection(const Circle &a, const Circle &b) {
Poly res;
int mode = isIntersect(a, b);
T d = abs(a.p - b.p);
if (mode == 4 or mode == 0)
return res;
if (mode == 3) {
T t = a.r / (a.r + b.r);
res.push_back(a.p + (b.p - a.p) * t);
return res;
}
if (mode == 1) {
if (b.r < a.r - eps) {
res.push_back(a.p + (b.p - a.p) * (a.r / d));
} else {
res.push_back(b.p + (a.p - b.p) * (b.r / d));
}
return res;
}
T rc = (a.r * a.r + d * d - b.r * b.r) / d / (T)2.;
T rs = sqrt(a.r * a.r - rc * rc);
if (a.r - abs(rc) < eps)
rs = 0;
Point e = unit(b.p - a.p);
res.push_back(a.p + rc * e + rs * e * Point(0, 1));
res.push_back(a.p + rc * e + rs * e * Point(0, -1));
return res;
}
Poly HalfplaneIntersection(vector<Line> &H) {
sort(ALL(H), [&](Line &l1, Line &l2) { return cmp(l1.dir, l2.dir); });
auto outside = [&](Line &L, Point p) -> bool {
return cross(L.dir, p - L.a) < -eps;
};
deque<Line> deq;
int sz = 0;
rep(i, 0, SZ(H)) {
while (sz > 1 and
outside(H[i], Intersection(deq[sz - 1], deq[sz - 2]))) {
deq.pop_back();
sz--;
}
while (sz > 1 and outside(H[i], Intersection(deq[0], deq[1]))) {
deq.pop_front();
sz--;
}
if (sz > 0 and fabs(cross(H[i].dir, deq[sz - 1].dir)) < eps) {
if (dot(H[i].dir, deq[sz - 1].dir) < 0) {
return {};
}
if (outside(H[i], deq[sz - 1].a)) {
deq.pop_back();
sz--;
} else
continue;
}
deq.push_back(H[i]);
sz++;
}
while (sz > 2 and outside(deq[0], Intersection(deq[sz - 1], deq[sz - 2]))) {
deq.pop_back();
sz--;
}
while (sz > 2 and outside(deq[sz - 1], Intersection(deq[0], deq[1]))) {
deq.pop_front();
sz--;
}
if (sz < 3)
return {};
deq.push_back(deq.front());
Poly ret;
rep(i, 0, sz) ret.push_back(Intersection(deq[i], deq[i + 1]));
return ret;
}
T Area(const Poly &a) {
T res = 0;
int n = a.size();
rep(i, 0, n) res += cross(a[i], a[(i + 1) % n]);
return fabs(res / (T)2.);
}
T Area(const Poly &a, const Circle &b) {
int n = a.size();
if (n < 3)
return (T).0;
auto rec = [&](auto self, const Circle &c, const Point &p1,
const Point &p2) {
Point va = c.p - p1, vb = c.p - p2;
T f = cross(va, vb), res = (T).0;
if (eq(f, (T).0))
return res;
if (max(abs(va), abs(vb)) < c.r + eps)
return f;
if (Dist(Segment(p1, p2), c.p) > c.r - eps)
return c.r * c.r * arg(vb * conj(va));
auto u = Intersection(c, Segment(p1, p2));
Poly sub;
sub.push_back(p1);
for (auto &x : u)
sub.push_back(x);
sub.push_back(p2);
rep(i, 0, sub.size() - 1) res += self(self, c, sub[i], sub[i + 1]);
return res;
};
T res = (T).0;
rep(i, 0, n) res += rec(rec, b, a[i], a[(i + 1) % n]);
return fabs(res / (T)2.);
}
T Area(const Circle &a, const Circle &b) {
T d = abs(a.p - b.p);
if (d >= a.r + b.r - eps)
return (T).0;
if (d <= abs(a.r - b.r) + eps) {
T r = min(a.r, b.r);
return M_PI * r * r;
}
T ath = acos((a.r * a.r + d * d - b.r * b.r) / d / a.r / (T)2.);
T res = a.r * a.r * (ath - sin(ath * 2) / (T)2.);
T bth = acos((b.r * b.r + d * d - a.r * a.r) / d / b.r / (T)2.);
res += b.r * b.r * (bth - sin(bth * 2) / (T)2.);
return fabs(res);
}
bool isConvex(const Poly &a) {
int n = a.size();
int cur, pre, nxt;
rep(i, 0, n) {
pre = (i - 1 + n) % n;
nxt = (i + 1) % n;
cur = i;
if (ccw(a[pre], a[cur], a[nxt]) == -1)
return 0;
}
return 1;
}
int isContained(const Poly &a,
const Point &b) { // 0:not contain,1:on edge,2:contain
bool res = 0;
int n = a.size();
rep(i, 0, n) {
Point p = a[i] - b, q = a[(i + 1) % n] - b;
if (p.Y > q.Y)
swap(p, q);
if (p.Y < eps and eps < q.Y and cross(p, q) > eps)
res ^= 1;
if (eq(cross(p, q), (T).0) and dot(p, q) < eps)
return 1;
}
return (res ? 2 : 0);
}
Poly ConvexHull(Poly &a) {
sort(ALL(a), [](const Point &p, const Point &q) {
return (eq(p.Y, q.Y) ? p.X < q.X : p.Y < q.Y);
});
a.erase(unique(ALL(a)), a.end());
int n = a.size(), k = 0;
Poly res(n * 2);
for (int i = 0; i < n; res[k++] = a[i++]) {
while (k >= 2 and
cross(res[k - 1] - res[k - 2], a[i] - res[k - 1]) < eps)
k--;
}
for (int i = n - 2, t = k + 1; i >= 0; res[k++] = a[i--]) {
while (k >= t and
cross(res[k - 1] - res[k - 2], a[i] - res[k - 1]) < eps)
k--;
}
res.resize(k - 1);
return res;
}
T Diam(const Poly &a) {
int n = a.size();
int x = 0, y = 0;
rep(i, 1, n) {
if (a[i].Y > a[x].Y)
x = i;
if (a[i].Y < a[y].Y)
y = i;
}
T res = abs(a[x] - a[y]);
int i = x, j = y;
do {
if (cross(a[(i + 1) % n] - a[i], a[(j + 1) % n] - a[j]) < 0)
i = (i + 1) % n;
else
j = (j + 1) % n;
chmax(res, abs(a[i] - a[j]));
} while (i != x or j != y);
return res;
}
Poly Cut(const Poly &a, const Line &l) {
int n = a.size();
Poly res;
rep(i, 0, n) {
Point p = a[i], q = a[(i + 1) % n];
if (ccw(l.a, l.b, p) != -1)
res.push_back(p);
if (ccw(l.a, l.b, p) * ccw(l.a, l.b, q) < 0)
res.push_back(Intersection(Line(p, q), l));
}
return res;
}
T Closest(Poly &a) {
int n = a.size();
if (n <= 1)
return 0;
sort(ALL(a), [&](Point a, Point b) {
return (eq(a.X, b.X) ? a.Y < b.Y : a.X < b.X);
});
Poly buf(n);
auto rec = [&](auto self, int lb, int rb) -> T {
if (rb - lb <= 1)
return (T)INF;
int mid = (lb + rb) >> 1;
auto x = a[mid].X;
T res = min(self(self, lb, mid), self(self, mid, rb));
inplace_merge(a.begin() + lb, a.begin() + mid, a.begin() + rb,
[&](auto p, auto q) { return p.Y < q.Y; });
int ptr = 0;
rep(i, lb, rb) {
if (abs(a[i].X - x) >= res)
continue;
rep(j, 0, ptr) {
auto sub = a[i] - buf[ptr - 1 - j];
if (sub.Y >= res)
break;
chmin(res, abs(sub));
}
buf[ptr++] = a[i];
}
return res;
};
return rec(rec, 0, n);
}
Circle Incircle(const Point &a, const Point &b, const Point &c) {
T A = abs(b - c), B = abs(c - a), C = abs(a - b);
Point p(A * a.X + B * b.X + C * c.X, A * a.Y + B * b.Y + C * c.Y);
p /= (A + B + C);
T r = Dist(Line(a, b), p);
return Circle(p, r);
}
Circle Circumcircle(const Point &a, const Point &b, const Point &c) {
Line l1((a + b) / (T)2., (a + b) / (T)2. + (b - a) * Point(0, 1));
Line l2((b + c) / (T)2., (b + c) / (T)2. + (c - b) * Point(0, 1));
Point p = Intersection(l1, l2);
return Circle(p, abs(p - a));
}
Poly tangent(const Point &a, const Circle &b) {
return Intersection(b, Circle(a, sqrt(norm(b.p - a) - b.r * b.r)));
}
vector<Line> tangent(const Circle &a, const Circle &b) {
vector<Line> res;
T d = abs(a.p - b.p);
if (eq(d, (T)0.))
return res;
Point u = unit(b.p - a.p);
Point v = u * Point(0, 1);
for (int t : {-1, 1}) {
T h = (a.r + b.r * t) / d;
if (eq(h * h, (T)1.)) {
res.push_back(Line(a.p + (h > 0 ? u : -u) * a.r,
a.p + (h > 0 ? u : -u) * a.r + v));
} else if (1 > h * h) {
Point U = u * h, V = v * sqrt(1 - h * h);
res.push_back(Line(a.p + (U + V) * a.r, b.p - (U + V) * (b.r * t)));
res.push_back(Line(a.p + (U - V) * a.r, b.p - (U - V) * (b.r * t)));
}
}
return res;
}
/**
* @brief Geometry
*/
const long double PI = 3.1415926535897932384626433832;
int main() {
int N;
Point V;
long double D, T;
cin >> N;
{
long double x, y;
cin >> x >> y;
V = Point(x,y);
}
V = unit(V);
cin >> D >> T;
Poly P(N);
rep(i,0,N) {
long double x, y;
cin >> x >> y;
P[i] = Point(x,y);
P[i] /= V;
}
bool check = false;
Segment XPLUS(Point(0.0L,0.0L), Point(0.0L, 100000.0L));
rep(i,0,N) {
Segment L(P[i], P[(i+1)%N]);
if (isIntersect(XPLUS, L)) check = true;
}
rep(i,0,N) {
if (P[i].real() >= 0.0L && abs(P[i].imag()) <= D) check = true;
}
if (check) {
long double MIN = PI, MAX = -PI;
rep(i,0,N) {
Poly Ret = tangent(Point(0.0L, 0.0L), Circle(P[i],D));
for (Point Q : Ret) {
chmin(MIN, arg(Q));
chmax(MAX, arg(Q));
}
}
ll Turn = T / (PI * 2.0L);
long double ANS = (MAX - MIN) * (long double)Turn;
T -= (PI * 2.0L) * (long double)Turn;
if (T <= MAX) ANS += T;
else if (T <= MIN + PI * 2) ANS += MAX;
else ANS += MAX + (T - (MIN + PI * 2));
printf("%.12Lf\n", ANS);
}
else {
long double MIN = PI, MAX = -PI;
rep(i,0,N) {
Poly Ret = tangent(Point(0.0L, 0.0L), Circle(P[i],D));
for (Point Q : Ret) {
long double R = arg(Q);
if (R < 0.0L) R += PI * 2.0L;
chmin(MIN, R);
chmax(MAX, R);
}
}
ll Turn = T / (PI * 2.0L);
long double ANS = (MAX - MIN) * (long double)Turn;
T -= (PI * 2.0L) * (long double)Turn;
if (T <= MIN) ANS += 0.0L;
else if (T <= MAX) ANS += T - MIN;
else ANS += (MAX - MIN);
printf("%.12Lf\n", ANS);
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4040kb
input:
3 1 0 1 1 1 2 2 1 2 2
output:
1.000000000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 4064kb
input:
3 1 0 1 2 1 2 2 1 2 2
output:
1.570796326795
result:
ok found '1.5707963', expected '1.5707963', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 4008kb
input:
3 1 0 1 10000 1 2 2 1 2 2
output:
2500.707752257475
result:
ok found '2500.7077523', expected '2500.7077523', error '0.0000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 4008kb
input:
3 10000 10000 1 10000 10000 9999 10000 10000 9999 10000
output:
0.384241300290
result:
ok found '0.3842413', expected '0.3842413', error '0.0000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 4068kb
input:
3 -10000 -10000 10000 10000 -10000 -9999 -10000 -10000 -9999 -10000
output:
2500.240670009608
result:
ok found '2500.2406700', expected '2500.2406700', error '0.0000000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 4040kb
input:
4 1 0 1 10000 -2 3400 -4 10000 -4 -10000 -2 -3400
output:
4999.219115408743
result:
ok found '4999.2191154', expected '4999.2191154', error '0.0000000'
Test #7:
score: 0
Accepted
time: 0ms
memory: 4040kb
input:
4 1 0 1 10000 -2 3300 -4 10000 -4 -10000 -2 -3300
output:
4999.200391854815
result:
ok found '4999.2003919', expected '4999.2003919', error '0.0000000'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3988kb
input:
4 -3040 2716 2147 2 -9033 -8520 -8999 -8533 -8988 -8511 -9004 -8495
output:
0.350830058342
result:
ok found '0.3508301', expected '0.3508301', error '0.0000000'
Test #9:
score: -100
Wrong Answer
time: 0ms
memory: 4032kb
input:
3 8168 -766 1549 1256 -3951 -6425 -3874 -6439 -3911 -6389
output:
266.059199383869
result:
wrong answer 1st numbers differ - expected: '84.8328612', found: '266.0591994', error = '2.1362752'