QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#122189 | #4799. Rotate Sum 3 | Isrothy | WA | 24ms | 19780kb | C++23 | 4.4kb | 2023-07-09 18:02:23 | 2023-07-09 18:02:24 |
Judging History
answer
#include <cassert>
#include <cmath>
#include <iostream>
#include <tuple>
#include <vector>
template<typename T> struct Point {
T x, y;
explicit Point(T x = 0, T y = 0) : x(x), y(y) {}
[[nodiscard]] auto len2() const {
return x * x + y * y;
}
[[nodiscard]] auto len() const {
return std::sqrt(len2());
}
};
template<typename T> using Vector = Point<T>;
template<typename T> using Line = std::pair<Point<T>, Point<T>>;
template<typename T, typename U> auto operator+(const Point<T> &a, const Point<U> &b) {
return Point(a.x + b.x, a.y + b.y);
}
template<typename T, typename U> auto operator-(const Point<T> &a, const Point<U> &b) {
return Point(a.x - b.x, a.y - b.y);
}
template<typename T, typename U> auto operator*(const Point<T> &a, const U &k) {
return Point(a.x * k, a.y * k);
}
template<typename T, typename U> auto operator*(const U &k, const Point<T> &a) {
return Point(a.x * k, a.y * k);
}
template<typename T, typename U> auto operator/(const Point<T> &a, const U &k) {
return Point(a.x / k, a.y / k);
}
template<typename T, typename U> auto det(const Point<T> &a, const Point<U> &b) {
return a.x * b.y - a.y * b.x;
}
template<typename T, typename U> auto dot(const Point<T> &a, const Point<U> &b) {
return a.x * b.x + a.y * b.y;
}
template<typename T>
auto point_line_distance(const Point<T> &p, const Point<T> &a, const Point<T> &b) {
return std::fabs(det(a - p, b - p) / (a - b).len());
}
template<typename T>
int line_line_intersection(
const Point<T> &a, const Point<T> &b, const Point<T> &c, const Point<T> &d, Point<double> &O
) {
if (det(b - a, d - c) == 0) {
if (det(b - a, c - a) == 0) {
return -1;
}
return 0;
}
auto s1 = det(d - a, c - a);
auto s2 = det(c - b, d - b);
O = a + 1.0 * s1 / (s1 + s2) * (b - a);
return 1;
}
const int M = 1e5 + 10;
Point<long long> P[M], Q[4 * M];
std::pair<long long, long long> a[4 * M];
bool mark[4 * M];
int p[4 * M];
int n;
int main() {
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
long long x, y;
scanf("%lld %lld", &x, &y);
P[i] = Point(2 * x, 2 * y);
}
for (int i = 0; i < n; ++i) {
Q[2 * i] = P[i];
Q[2 * i + 1] = (P[i] + P[(i + 1) % n]) / 2;
}
for (int i = 0; i < 2 * n; ++i) {
Q[i + 2 * n] = Q[i];
}
for (int i = 0; i < 4 * n; ++i) {
Point A = Q[(i - 1 + 4 * n) % (4 * n)];
Point B = Q[(i + 1) % (4 * n)];
a[i] = i & 1 ? std::make_pair((A - B).len2(), 0LL)
: std::make_pair(dot(Q[i] - A, Q[i] - B), det(Q[i] - A, Q[i] - B));
}
// for (int i = 0; i < 2 * n; ++i) {
// printf("%lld\n", a[i]);
// }
std::vector<Line<long long>> axis;
for (int i = 0, l = 0, r = -1; i < 4 * n; ++i) {
int k = r < i ? 0 : std::min(p[l + r - i], r - i);
while (0 <= i - k - 1 && i + k + 1 < 4 * n && a[i - k - 1] == a[i + k + 1]) {
++k;
}
p[i] = k;
if (r < i + k) {
l = i - k;
r = i + k;
}
// printf("%d %d\n", i, p[i]);
if (p[i] >= n) {
if (!mark[i] && !mark[i - n]) {
mark[i] = true;
mark[i + n] = true;
axis.emplace_back(Q[i], Q[i + n]);
}
}
}
if (axis.empty()) {
puts("0");
} else if (axis.size() == 1) {
double ans = 0;
for (int i = 0; i < n; ++i) {
auto v = P[i] - P[(i + 1) % n];
auto u = axis[0].first - axis[0].second;
auto r1 = point_line_distance(P[i], axis[0].first, axis[0].second);
auto r2 = point_line_distance(P[(i + 1) % n], axis[0].first, axis[0].second);
auto h = fabs(dot(v, u)) / u.len();
// printf("%lf %lf %lf\n", r1, r2, h);
ans += M_PI * (r1 * r1 + r2 * r2 + r1 * r2) * h / 3;
}
printf("%.10lf\n", ans / 16);
} else {
Point<double> O;
int ret = line_line_intersection(
axis[0].first, axis[0].second, axis[1].first, axis[1].second, O
);
// assert(ret == 1);
double r = 0;
for (int i = 0; i < n; ++i) {
r = std::max(r, (P[i] - O).len());
}
printf("%.10lf\n", 4.0 / 3.0 * M_PI * r * r * r / 8);
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 14840kb
input:
3 0 -1 1 0 0 1
output:
1.0471975512
result:
ok found '1.0471976', expected '1.0471976', error '0.0000000'
Test #2:
score: 0
Accepted
time: 3ms
memory: 15376kb
input:
3 1 1 4 5 1 4
output:
0
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #3:
score: 0
Accepted
time: 3ms
memory: 14904kb
input:
10 -54592357 -80406461 -54592497 -80409914 -54583785 -80448527 -54573150 -80452302 -54571418 -80445561 -54573057 -80436942 -54574710 -80428961 -54576431 -80421748 -54581146 -80413624 -54586843 -80406612
output:
0
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #4:
score: 0
Accepted
time: 1ms
memory: 14836kb
input:
100 19218707 41938436 19227173 41936741 19236439 41934895 19244714 41933329 19263050 41933508 19269952 41935468 19276958 41938057 19283547 41941029 19290649 41944891 19298015 41949938 19301176 41952107 19308530 41957785 19315067 41963572 19323587 41972122 19331125 41980143 19339499 41989094 19341411...
output:
0
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 14712kb
input:
1000 -40710097 -68387840 -40713262 -68382547 -40715876 -68378183 -40720034 -68371279 -40724775 -68363579 -40730740 -68353973 -40736549 -68344830 -40739819 -68339713 -40742687 -68335270 -40746895 -68328767 -40752947 -68319823 -40754886 -68316968 -40761079 -68308110 -40767747 -68298732 -40770472 -6829...
output:
0
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #6:
score: 0
Accepted
time: 5ms
memory: 17220kb
input:
10000 84849929 -57126112 84841472 -57123352 84836897 -57121859 84827816 -57118905 84819535 -57116213 84810908 -57113420 84809250 -57112891 84802608 -57110788 84797710 -57109239 84789766 -57106738 84783187 -57104673 84773775 -57101720 84766522 -57099445 84757149 -57096507 84751370 -57094702 84745393 ...
output:
0
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #7:
score: 0
Accepted
time: 1ms
memory: 14164kb
input:
20000 36695920 63855096 36699821 63853995 36702135 63853342 36706473 63852120 36712051 63850550 36717151 63849119 36721923 63847781 36730794 63845294 36739373 63842890 36745062 63841296 36751484 63839501 36760104 63837093 36769910 63834359 36779620 63831652 36788710 63829118 36797797 63826588 368057...
output:
0
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #8:
score: 0
Accepted
time: 13ms
memory: 19616kb
input:
50000 63220612 55859143 63226689 55860975 63228549 55861536 63237384 55864204 63246036 55866818 63253128 55868961 63262941 55871927 63272384 55874783 63278109 55876515 63285718 55878817 63289955 55880101 63297340 55882339 63305978 55884958 63313100 55887118 63321418 55889645 63330759 55892485 633335...
output:
0
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #9:
score: 0
Accepted
time: 18ms
memory: 19244kb
input:
100000 6150629 209064536 6145207 209063168 6135217 209060644 6125551 209058201 6115985 209055782 6108484 209053885 6099150 209051524 6093683 209050141 6084620 209047848 6081814 209047138 6072408 209044758 6064213 209042684 6055932 209040588 6047114 209038356 6037530 209035930 6028054 209033531 60199...
output:
0
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #10:
score: 0
Accepted
time: 10ms
memory: 19528kb
input:
99989 -135597084 24675451 -135596066 24669344 -135594745 24661432 -135593849 24656066 -135593366 24653174 -135591982 24644890 -135590618 24636739 -135590005 24633076 -135588796 24625860 -135587482 24618020 -135586605 24612788 -135585381 24605487 -135583879 24596531 -135583397 24593658 -135582102 245...
output:
0
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #11:
score: 0
Accepted
time: 1ms
memory: 14456kb
input:
12432 -53030605 62756639 -53020643 62747841 -53011057 62739377 -53003690 62732873 -52999478 62729161 -52992709 62723198 -52986581 62717802 -52979396 62711476 -52974388 62707069 -52973366 62706172 -52970127 62703330 -52965879 62699603 -52955918 62690870 -52948653 62684509 -52940428 62677331 -52931644...
output:
0
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #12:
score: 0
Accepted
time: 13ms
memory: 19592kb
input:
95846 96281192 -1877350 96286947 -1871034 96291470 -1866068 96300515 -1856135 96306553 -1849500 96315540 -1839624 96320958 -1833670 96328658 -1825206 96336295 -1816811 96341317 -1811290 96348753 -1803115 96355968 -1795181 96360393 -1790315 96366306 -1783812 96372117 -1777421 96375231 -1773996 963804...
output:
0
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #13:
score: 0
Accepted
time: 11ms
memory: 19596kb
input:
77877 134743677 56655124 134749156 56665110 134753149 56672389 134758418 56681995 134761944 56688425 134766712 56697123 134770923 56704806 134775444 56713057 134779077 56719688 134782792 56726469 134788085 56736131 134789440 56738605 134793460 56745946 134798926 56755928 134803171 56763683 134807060...
output:
0
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #14:
score: 0
Accepted
time: 12ms
memory: 17404kb
input:
44722 -1000000000 -1000000000 -999999999 -999999999 -999999998 -999999996 -999999997 -999999991 -999999996 -999999984 -999999995 -999999975 -999999994 -999999964 -999999993 -999999951 -999999992 -999999936 -999999991 -999999919 -999999990 -999999900 -999999989 -999999879 -999999988 -999999856 -99999...
output:
0
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #15:
score: 0
Accepted
time: 4ms
memory: 17020kb
input:
30000 -999999999 -999999999 -999999997 -999999991 -999999995 -999999975 -999999993 -999999951 -999999990 -999999900 -999999989 -999999879 -999999987 -999999831 -999999984 -999999744 -999999983 -999999711 -999999982 -999999676 -999999980 -999999600 -999999979 -999999559 -999999977 -999999471 -9999999...
output:
0
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #16:
score: 0
Accepted
time: 7ms
memory: 14384kb
input:
23333 -1000000000 -1000000000 -999999996 -999999984 -999999994 -999999964 -999999993 -999999951 -999999992 -999999936 -999999991 -999999919 -999999986 -999999804 -999999985 -999999775 -999999983 -999999711 -999999979 -999999559 -999999977 -999999471 -999999976 -999999424 -999999975 -999999375 -99999...
output:
0
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #17:
score: 0
Accepted
time: 0ms
memory: 15408kb
input:
10 -999998304 -997123584 -999995033 -975328911 -999991449 -926880399 -999989625 -892359375 -999986588 -820118256 -999985688 -795166656 -999983492 -727485936 -999982787 -703712631 -999975967 -422414911 -999964606 252735236
output:
0
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #18:
score: 0
Accepted
time: 3ms
memory: 13636kb
input:
4 0 -1000000000 1 -1 2 999999999 1 0
output:
0
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #19:
score: 0
Accepted
time: 1ms
memory: 15020kb
input:
12 66207546 277078203 66231235 277049680 66236583 277045669 66270598 277030914 66302758 277017619 66330166 277008238 66376807 277002726 66421946 277004478 66139790 277216095 66150747 277172271 66169098 277129039 66185778 277105354
output:
3678257734031381.5000000000
result:
ok found '3678257734031381.5000000', expected '3678257734031382.0000000', error '0.0000000'
Test #20:
score: 0
Accepted
time: 0ms
memory: 14256kb
input:
102 -214419393 270555934 -214412973 270566017 -214400819 270585311 -214376473 270642208 -214363763 270677346 -214348006 270739418 -214339576 270772958 -214324466 270833912 -214311353 270916345 -214298660 271006631 -214288849 271092751 -214280642 271182973 -214275540 271280266 -214275929 271363784 -2...
output:
6457421713045693440.0000000000
result:
ok found '6457421713045693440.0000000', expected '6457421713045695488.0000000', error '0.0000000'
Test #21:
score: 0
Accepted
time: 3ms
memory: 14492kb
input:
1001 -518856696 367668466 -518851942 367707590 -518848267 367738199 -518843392 367780072 -518841758 367806560 -518840150 367834270 -518839509 367847939 -518837679 367896197 -518837227 367908211 -518835756 367953090 -518834993 367977927 -518833598 368028178 -518832322 368076762 -518831195 368122711 -...
output:
995850288231111720960.0000000000
result:
ok found '995850288231111720960.0000000', expected '995850288231110803456.0000000', error '0.0000000'
Test #22:
score: 0
Accepted
time: 1ms
memory: 15016kb
input:
10002 -435787598 215644243 -435750530 215616649 -435712097 215588064 -435665253 215553314 -435642490 215536470 -435596515 215502457 -435549583 215467777 -435501328 215432124 -435484225 215419512 -435449441 215393887 -435419551 215371884 -435381598 215344006 -435369357 215335023 -435347978 215319348 ...
output:
1239358451873427100794880.0000000000
result:
ok found '1239358451873427100794880.0000000', expected '1239358451873428979843072.0000000', error '0.0000000'
Test #23:
score: 0
Accepted
time: 7ms
memory: 17652kb
input:
20001 157994472 29380131 158020164 29359872 158049453 29336805 158051862 29334909 158075181 29316558 158093559 29302098 158111787 29287758 158137422 29267613 158160141 29249763 158189031 29227071 158214330 29207217 158238372 29188368 158264790 29167674 158289414 29148402 158309739 29132505 158334225...
output:
1666664332307088919232512.0000000000
result:
ok found '1666664332307088919232512.0000000', expected '1666664332307093214199808.0000000', error '0.0000000'
Test #24:
score: 0
Accepted
time: 7ms
memory: 16552kb
input:
50002 -355463812 -37892508 -355467668 -37890676 -355484408 -37882724 -355490540 -37879812 -355513156 -37869076 -355518286 -37866642 -355542542 -37855142 -355563662 -37845130 -355589462 -37832914 -355615938 -37820378 -355622994 -37817038 -355647684 -37805356 -355669582 -37794998 -355694176 -37783372 ...
output:
21401706260728714601955328.0000000000
result:
ok found '21401706260728714601955328.0000000', expected '21401706260728779026464768.0000000', error '0.0000000'
Test #25:
score: 0
Accepted
time: 16ms
memory: 19708kb
input:
92437 -236983267 -225951646 -236961708 -225951429 -236952273 -225951334 -236947808 -225951289 -236939095 -225951200 -236919035 -225950995 -236897861 -225950778 -236877227 -225950566 -236853113 -225950314 -236839457 -225950171 -236821547 -225949981 -236815902 -225949921 -236794785 -225949695 -2367773...
output:
67555026409586713853689856.0000000000
result:
ok found '67555026409586713853689856.0000000', expected '67555026409586713853689856.0000000', error '0.0000000'
Test #26:
score: 0
Accepted
time: 17ms
memory: 19724kb
input:
100000 -39496740 -315509129 -39487084 -315503653 -39478294 -315498664 -39468980 -315493377 -39462501 -315489699 -39458473 -315487412 -39455460 -315485701 -39446388 -315480549 -39437380 -315475433 -39432422 -315472617 -39425199 -315468513 -39416209 -315463405 -39408432 -315458986 -39401602 -315455104...
output:
7518927930183708183625728.0000000000
result:
ok found '7518927930183708183625728.0000000', expected '7518927930183777976844288.0000000', error '0.0000000'
Test #27:
score: 0
Accepted
time: 16ms
memory: 19780kb
input:
100000 -210600675 278803029 -210609734 278802522 -210627753 278801513 -210646311 278800473 -210657119 278799867 -210665042 278799422 -210678943 278798641 -210693849 278797803 -210695521 278797709 -210706025 278797117 -210723413 278796137 -210737944 278795318 -210751356 278794562 -210766761 278793693...
output:
21431351219308204767838208.0000000000
result:
ok found '21431351219308204767838208.0000000', expected '21431351219308144638296064.0000000', error '0.0000000'
Test #28:
score: 0
Accepted
time: 12ms
memory: 19640kb
input:
99999 218789668 -30062233 218794627 -30062475 218801690 -30062819 218806557 -30063056 218816411 -30063535 218824584 -30063932 218833009 -30064340 218838547 -30064608 218842640 -30064806 218851370 -30065228 218859212 -30065606 218863641 -30065819 218873133 -30066275 218880895 -30066647 218887844 -300...
output:
7527184527576958142251008.0000000000
result:
ok found '7527184527576958142251008.0000000', expected '7527184527576951699800064.0000000', error '0.0000000'
Test #29:
score: 0
Accepted
time: 15ms
memory: 19644kb
input:
100000 82919048 -59332292 82916010 -59318408 82914444 -59311256 82910724 -59294272 82906424 -59274644 82902060 -59254728 82901298 -59251252 82897114 -59232174 82893492 -59215662 82891602 -59207046 82888736 -59193982 82885472 -59179104 82881702 -59161920 82879974 -59154046 82876596 -59138654 82875350...
output:
59343686935899513215254528.0000000000
result:
ok found '59343686935899513215254528.0000000', expected '59343686935900114510675968.0000000', error '0.0000000'
Test #30:
score: 0
Accepted
time: 16ms
memory: 19652kb
input:
99999 -402380358 -107427468 -402383014 -107437774 -402386031 -107449481 -402389658 -107463560 -402393296 -107477692 -402397214 -107492914 -402400465 -107505547 -402403082 -107515718 -402407128 -107531454 -402410352 -107543998 -402411755 -107549457 -402413647 -107556819 -402417630 -107572336 -4024205...
output:
21594566007453001529163776.0000000000
result:
ok found '21594566007453001529163776.0000000', expected '21594566007452941399621632.0000000', error '0.0000000'
Test #31:
score: 0
Accepted
time: 24ms
memory: 19656kb
input:
99999 -303286690 188419090 -303288556 188407794 -303290704 188394790 -303293491 188377917 -303296036 188362506 -303297724 188352282 -303300256 188336940 -303301127 188331657 -303303320 188318354 -303304980 188308280 -303307691 188291827 -303309017 188283775 -303310881 188272455 -303312454 188262902 ...
output:
21261977991847002461175808.0000000000
result:
ok found '21261977991847002461175808.0000000', expected '21261977991846804892680192.0000000', error '0.0000000'
Test #32:
score: -100
Wrong Answer
time: 0ms
memory: 14620kb
input:
4 1000000000 1000000000 -1000000000 1000000000 -1000000000 -1000000000 1000000000 -1000000000
output:
7377357352013433654341542084608.0000000000
result:
wrong answer 1st numbers differ - expected: '11847687835088975981023592448.0000000', found: '7377357352013433654341542084608.0000000', error = '621.6832995'