QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#808077 | #9869. Horizon Scanning | Hiraethsoul# | AC ✓ | 50ms | 14696kb | C++23 | 3.1kb | 2024-12-10 16:54:28 | 2024-12-10 16:54:36 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
struct BaseVector2 : public std::pair<int, int>
{
#define x first
#define y second
using std::pair<int, int>::pair;
BaseVector2 operator-(BaseVector2 a) const
{
return BaseVector2(this->x - a.x, this->y - a.y);
}
int operator*(BaseVector2 a) const
{
return this->x * a.x + this->y * a.y;
}
int operator%(BaseVector2 a) const
{
return this->x * a.y - this->y * a.x;
}
friend std::istream &operator>>(std::istream &in, BaseVector2 &p)
{
return in >> p.x >> p.y;
}
};
int dis2(BaseVector2 a, BaseVector2 b = BaseVector2(0, 0))
{
BaseVector2 p = a - b;
return p * p;
}
using Point = BaseVector2;
using Vector = Point;
int sgn(BaseVector2 p)
{
if ((p.x < 0 or p.x == 0 and p.y > 0))
{
return true;
}
return false;
}
bool polarCmp(Vector p, Vector q)
{
if (sgn(p) == sgn(q))
{
if (p % q == 0)
{
return dis2(p) < dis2(q);
}
else
{
return p % q > 0;
}
}
return sgn(p) < sgn(q);
}
const long double pi = acosl(-1.0);
long double getAngle(Point a, Point b, Point c)
{
auto v1 = b - a, v2 = c - a;
return atan2l(v1 % v2, v1 * v2);
}
void solve()
{
int n, k;
std::cin >> n >> k;
std::vector<Point> t(n);
for (int i = 0; i < n; ++i)
{
std::cin >> t[i];
}
std::sort(begin(t), end(t), polarCmp);
std::vector<Point> s(2 * n + 1);
for (int i = 0; i < n; ++i)
{
s[i] = t[i];
s[i + n] = t[i];
}
long double ans = 0;
std::vector<int> vis(2 * n + 1, 0);
if (s[0] % s[n - 1] == 0 and s[0] * s[n - 1] >= 0 or k == n)
{
ans = 2 * pi;
std::cout << std::fixed << std::setprecision(20) << ans << '\n';
return;
}
int i = 0, j = 0;
int cnt = 0;
while (i < n)
{
while (i < n and s[i + 1] % s[i] == 0 and s[i + 1] * s[i] >= 0)
{
if (vis[i])
{
--cnt;
vis[i] = 0;
}
++i;
}
if (vis[i])
{
vis[i] = 0;
--cnt;
}
if (j <= i)
{
j = i + 1;
}
while (j < n + i and cnt < k and (s[j] % s[i] != 0 or s[j] % s[i] == 0 and s[j] * s[i] < 0))
{
++cnt;
vis[j] = 1;
++j;
}
if (cnt < k)
{
ans = 2 * pi;
}
else
{
long double val = getAngle(BaseVector2(0, 0), s[i], s[j - 1]);
if (val < 0)
{
val += 2 * pi;
}
ans = std::max(ans, val);
}
++i;
}
std::cout << std::fixed << std::setprecision(20) << ans << '\n';
}
signed main()
{
std::ios::sync_with_stdio(0);
std::cin.tie(0);
int t;
std::cin >> t;
while (t--)
{
solve();
}
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3860kb
input:
5 1 1 0 1 8 2 1 0 1 1 0 1 -1 1 -1 0 -1 -1 0 -1 1 -1 4 2 -1 1 0 1 0 2 1 1 4 2 -1000000000 0 -998244353 1 998244353 1 1000000000 0 3 1 0 1 0 2 0 -1
output:
6.28318530717958647703 1.57079632679489661926 5.49778714378213816723 3.14159265459155197329 3.14159265358979323851
result:
ok 5 numbers
Test #2:
score: 0
Accepted
time: 25ms
memory: 3868kb
input:
10000 16 1 -10 -6 -5 -6 -4 9 -2 5 -2 10 1 -7 1 -5 1 6 3 1 4 -9 6 -10 6 -3 6 1 8 -5 8 -4 9 -4 17 4 -9 2 -8 -4 -8 -3 -8 -1 -6 -2 -6 -1 -6 8 -5 -8 -5 10 -4 8 -2 -8 4 -9 4 0 5 -3 8 -5 9 -2 10 10 10 6 -7 2 -4 6 -2 -7 -2 -1 -1 7 1 -9 1 8 3 -4 7 -4 9 -2 14 3 -9 10 -8 -10 -8 -8 -6 -7 -6 -5 -1 -7 -1 -2 0 -1 ...
output:
1.69299149748625167350 2.57486343606628689091 4.65275826725352046860 2.77263310738393677361 5.74276580690900232155 4.85769899102039198454 3.41989231259490458997 2.81279996208483885922 6.28318530717958647703 6.28318530717958647703 5.11728076666977328094 6.14678270277863904834 3.84208902353751959730 2...
result:
ok 10000 numbers
Test #3:
score: 0
Accepted
time: 28ms
memory: 3988kb
input:
10000 19 7 -10 -6 -10 5 -3 0 -2 -5 -1 1 -1 6 0 3 0 7 1 9 3 -3 3 3 3 8 4 -1 5 8 6 -3 7 -5 7 4 8 10 9 -5 15 15 -9 -1 -8 6 -7 9 -6 -3 -4 -9 -1 -3 -1 8 1 -8 1 -7 3 -2 3 1 6 -9 7 -10 7 0 10 -9 10 3 -7 -1 -6 -2 -6 10 -5 2 -4 2 -3 -7 -2 -9 1 -3 3 4 7 7 15 4 -8 -8 -8 8 -7 0 -7 10 -6 -7 -5 6 -1 -3 -1 0 1 -2 ...
output:
3.92699081698724154809 6.28318530717958647703 3.36026159946373520070 2.67794504458898712223 3.77038894000522619310 1.76258446878160168390 3.84025247831125643634 5.49778714378213816723 2.03444393579570273543 1.81577498992176077335 4.34718753059651682232 6.14128825257542255425 5.17603658938549597394 5...
result:
ok 10000 numbers
Test #4:
score: 0
Accepted
time: 28ms
memory: 3940kb
input:
10000 18 12 -10 -4 -10 7 -8 -10 -7 -4 -6 5 -6 7 -5 0 -2 -7 -1 2 -1 10 0 2 1 1 3 -2 5 3 5 5 6 -3 8 -3 9 -2 10 1 -10 -9 -7 -7 -5 2 -4 -7 -3 1 3 1 3 3 5 -4 9 2 9 6 11 2 -8 1 -8 6 -7 -2 -6 0 -5 0 -1 -9 2 -8 3 5 6 0 10 -2 10 6 20 9 -10 -6 -10 6 -9 -8 -7 5 -6 -4 -4 -8 -2 -10 -2 -3 -2 4 -1 1 2 -5 3 -2 5 -6...
output:
4.90978454023457061605 1.97568811307998004254 1.98686083251871933961 3.92699081698724154809 3.69775888371024621742 6.28318530717958647703 6.14128825257542255425 6.19387131418636427199 5.80535425218747162205 6.25289154726081137549 5.72887781097803524752 3.09009184263856776084 1.89254688119153881266 5...
result:
ok 10000 numbers
Test #5:
score: 0
Accepted
time: 28ms
memory: 3844kb
input:
10000 19 7 -10 -1 -8 2 -7 -10 -6 6 -4 7 -3 -5 -3 1 -3 8 -2 4 -1 -7 0 -8 0 9 1 -10 2 1 2 3 3 5 6 -4 10 2 10 3 14 10 -8 2 -6 0 -5 -10 -5 10 -4 7 -3 -6 -2 -6 1 4 1 6 2 -1 3 -6 8 -4 9 -10 10 -1 12 8 -9 5 -7 2 -4 2 0 -2 0 5 1 6 3 2 4 9 5 5 7 -6 9 -9 9 2 19 12 -10 -10 -10 2 -9 -6 -8 2 -7 -5 -6 8 -4 1 -1 -...
output:
3.23931956094851196946 5.27570524187665800160 5.30039158393225740907 5.38712992260824252103 5.88839418747982496025 4.11731935667914868918 1.13838855122435877922 1.51529782154917978365 6.14765759319408574505 6.15883031263282504190 2.57486343606628689091 5.94016136675888308015 1.60851427926176083409 4...
result:
ok 10000 numbers
Test #6:
score: 0
Accepted
time: 28ms
memory: 3876kb
input:
10000 11 10 -10 -1 -9 4 -9 10 -7 -7 -5 4 -4 -1 -2 -10 0 -7 0 5 3 3 3 5 12 12 -9 6 -9 8 -3 -2 -2 2 0 -4 1 0 2 -3 3 5 5 -2 7 -1 10 3 10 9 14 12 -10 0 -9 -3 -9 1 -9 10 -8 -1 -8 7 -6 -1 -1 -6 -1 2 1 -1 3 -7 4 9 9 -3 10 1 10 4 -9 -3 -7 -1 -6 -10 -3 -2 -3 7 2 -2 2 3 5 2 6 9 9 6 10 2 -9 -9 -9 6 -8 3 -5 -9 ...
output:
6.13787529654388435037 6.28318530717958647703 6.11803662976495963872 3.20034847630551593151 2.65375621493015080099 6.25378201897558136163 3.60524026259059935480 3.55981698316902233975 1.50914615615563758389 5.92754942287882667651 6.25879989800686793982 2.62244653934327028662 4.39383330329662278408 5...
result:
ok 10000 numbers
Test #7:
score: 0
Accepted
time: 29ms
memory: 3928kb
input:
10000 14 1 -100 13 -96 -31 -82 -92 -77 -98 -50 1 -14 -57 -14 -31 -11 64 -8 75 9 68 25 100 54 -36 59 13 93 31 19 19 -76 -39 -60 95 -51 18 -39 11 -21 -46 -6 -94 -5 83 -3 -34 -3 72 0 -55 3 79 14 17 23 -88 32 37 50 70 61 -5 62 -43 84 -100 97 -50 13 7 -99 -63 -68 -87 -24 62 -20 -18 -2 -66 7 -49 13 -21 15...
output:
1.27130939746127916005 6.28318530717958647703 5.22251472073649891182 6.00306570356891767547 3.92587213546467918963 5.54652899509206975771 3.21031492371172300407 3.03993004992372313857 4.22753178179442666617 3.03201966573687692157 2.19121523381819052691 3.03900809036774125892 4.33132715063550357507 6...
result:
ok 10000 numbers
Test #8:
score: 0
Accepted
time: 22ms
memory: 3988kb
input:
100 1413 755 -30 -30 -30 -28 -30 -27 -30 -26 -30 -21 -30 -12 -30 -10 -30 -8 -30 -5 -30 -1 -30 2 -30 4 -30 7 -30 9 -30 17 -30 19 -30 20 -30 23 -30 24 -30 30 -29 -29 -29 -23 -29 -15 -29 0 -29 4 -29 5 -29 9 -29 10 -29 11 -29 12 -29 14 -29 16 -29 17 -29 22 -29 27 -29 28 -28 -28 -28 -25 -28 -23 -28 -22 -...
output:
3.58911262874696311825 2.97975522235137031419 0.28379410920832784563 2.03502770689109314223 4.88798114233487010234 1.00406710927139027165 4.74570997626293705502 5.32559632925919914335 4.31027496473292711949 5.60338367941383051415 1.57980509208531353315 4.32964547053911433467 5.54722209679409179479 1...
result:
ok 100 numbers
Test #9:
score: 0
Accepted
time: 32ms
memory: 4512kb
input:
20 9045 8319 -1000 -986 -1000 -683 -1000 -430 -1000 -292 -1000 53 -1000 667 -999 -855 -999 -350 -999 -174 -999 -51 -999 -43 -999 235 -999 465 -999 530 -998 -997 -998 -311 -998 21 -998 44 -998 182 -997 -313 -997 -195 -997 -13 -997 412 -997 425 -996 -542 -996 -348 -996 -126 -996 -59 -996 -40 -996 84 -...
output:
5.91151100390402647411 3.74386851513771177374 2.53848285831534758962 2.15996735885788730940 4.29503770957234460703 4.77167447479618288915 4.68240781260193612151 5.07898439417457466926 1.60080182141066391694 3.34040254563670497689 3.36879252825034920891 2.11301602823006157432 4.85539941013267011471 4...
result:
ok 20 numbers
Test #10:
score: 0
Accepted
time: 37ms
memory: 13636kb
input:
1 166347 18723 -1000 -979 -1000 -975 -1000 -928 -1000 -914 -1000 -898 -1000 -889 -1000 -876 -1000 -873 -1000 -858 -1000 -840 -1000 -838 -1000 -801 -1000 -783 -1000 -744 -1000 -738 -1000 -733 -1000 -713 -1000 -712 -1000 -695 -1000 -689 -1000 -680 -1000 -675 -1000 -671 -1000 -646 -1000 -643 -1000 -608...
output:
0.85144917898051572161
result:
ok found '0.8514492', expected '0.8514492', error '0.0000000'
Test #11:
score: 0
Accepted
time: 37ms
memory: 12748kb
input:
1 154903 84960 -1000 -979 -1000 -965 -1000 -956 -1000 -945 -1000 -920 -1000 -901 -1000 -878 -1000 -860 -1000 -858 -1000 -709 -1000 -693 -1000 -648 -1000 -619 -1000 -602 -1000 -579 -1000 -474 -1000 -473 -1000 -454 -1000 -443 -1000 -427 -1000 -407 -1000 -403 -1000 -384 -1000 -351 -1000 -279 -1000 -244...
output:
3.53892668538316640826
result:
ok found '3.5389267', expected '3.5389267', error '0.0000000'
Test #12:
score: 0
Accepted
time: 30ms
memory: 13008kb
input:
1 158037 96343 -1000 -1000 -1000 -905 -1000 -881 -1000 -833 -1000 -804 -1000 -803 -1000 -782 -1000 -775 -1000 -765 -1000 -759 -1000 -756 -1000 -748 -1000 -722 -1000 -674 -1000 -669 -1000 -630 -1000 -610 -1000 -573 -1000 -443 -1000 -411 -1000 -409 -1000 -403 -1000 -388 -1000 -366 -1000 -349 -1000 -33...
output:
3.97202877832588092705
result:
ok found '3.9720288', expected '3.9720288', error '0.0000000'
Test #13:
score: 0
Accepted
time: 38ms
memory: 3928kb
input:
10000 17 12 -853202371 684059854 -659446544 -924219854 -418025687 117998679 -399757126 -365708913 -331597239 -270896799 -204989763 869548983 -118492298 963842298 -77481232 672198731 45930201 -58234380 52605147 -900097542 78371985 940503934 235210685 595759114 391284089 234315077 416229789 -827244230...
output:
5.39852511003435244505 5.37390787485642362374 1.17357817287416182569 1.54436525950838584784 3.77828864940306856520 3.57047158685250464035 6.28297485883615878339 5.09592520281510049339 2.98757824655085039317 2.30556650580152931946 3.39078416418203492581 5.78547323812813288867 4.81096361226396474278 0...
result:
ok 10000 numbers
Test #14:
score: 0
Accepted
time: 37ms
memory: 3876kb
input:
1000 133 108 -994106086 710243426 -991027749 -548437545 -983318226 -917527783 -943673956 -368162275 -935819096 616077188 -928022346 487569673 -924213856 -369318351 -914827619 426646545 -883935180 590882141 -870015071 -270471333 -834927107 -211343853 -829266515 354007200 -788041913 -60481736 -7822837...
output:
5.74280179214319556977 1.91536423984179382898 3.80434579810800695176 1.79191627053112991126 3.16952067063520373578 6.07864621461560185539 3.78606745951064125114 3.66596907268785624640 6.22658345297044581385 5.90215219261039025344 5.94431570929567669112 0.71516768704310207649 3.83157425297719989488 1...
result:
ok 1000 numbers
Test #15:
score: 0
Accepted
time: 39ms
memory: 3936kb
input:
100 1367 924 -999416811 990355566 -997656126 346133696 -997071616 -657387469 -996176051 12622726 -995720693 334093112 -995478093 891631278 -994503890 341858449 -994297596 499383911 -993234202 533518057 -991636838 -4170504 -990563582 -407186200 -989454027 653116272 -989132124 -780605454 -988073521 -1...
output:
4.50515349061768910922 2.71255893262747842893 5.83967858098196691439 6.02297711145261552030 0.46160604310141639648 0.98699123321252298411 1.32197084883432319855 1.92584174583805948155 5.50860835334991086418 4.64635533129787900875 2.28767741020770681783 2.18487258779632965294 4.80940919180683891130 0...
result:
ok 100 numbers
Test #16:
score: 0
Accepted
time: 43ms
memory: 5056kb
input:
10 13806 4955 -999669776 933068103 -999542354 721337508 -999499427 357140594 -999429088 -925180511 -999334813 -145726169 -999291694 -886327684 -999281647 811188099 -999145269 860687107 -998961821 -979442436 -998769313 446186367 -998591455 658309173 -998539751 -569480843 -998479467 279850955 -9984754...
output:
2.41708046803397828915 6.16119222907872696833 3.96002037684223525131 3.99436179290459344397 2.55155083615552036942 0.52272383678099888099 4.09784382785422951565 6.21038266315892891704 5.98172802925396587511 0.77722368589060050525
result:
ok 10 numbers
Test #17:
score: 0
Accepted
time: 31ms
memory: 10180kb
input:
1 112596 94970 -999980219 399324466 -999932413 952114487 -999894556 -951211102 -999891030 -996222974 -999864824 412806264 -999853190 -269700371 -999845814 -23906803 -999841507 -459154880 -999825178 716247149 -999761774 -154047106 -999729655 -171480333 -999709604 -666447277 -999704754 -22442485 -9996...
output:
5.44259387934385180027
result:
ok found '5.4425939', expected '5.4425939', error '0.0000000'
Test #18:
score: 0
Accepted
time: 43ms
memory: 13204kb
input:
1 161568 13252 -999991243 -113889211 -999976572 -361096764 -999970140 -505012445 -999960654 600963873 -999959339 -269932510 -999956568 734634576 -999941447 716485764 -999940305 64397798 -999939982 746532931 -999939921 995002380 -999932747 185078659 -999927136 585216518 -999914684 898656539 -99990452...
output:
0.64247459068649763545
result:
ok found '0.6424746', expected '0.6424746', error '0.0000000'
Test #19:
score: 0
Accepted
time: 50ms
memory: 14696kb
input:
1 186192 126483 -999998234 974001047 -999976292 -133179660 -999967957 112862981 -999957851 70030467 -999951528 743907713 -999931316 66002112 -999907988 888991267 -999905412 470798211 -999903986 -103943462 -999900422 255729004 -999898174 917068198 -999884392 -183592605 -999880179 -650076162 -99987469...
output:
4.40124568411901000283
result:
ok found '4.4012457', expected '4.4012457', error '0.0000000'
Test #20:
score: 0
Accepted
time: 31ms
memory: 3848kb
input:
1000 133 9 -10 -839744900 -10 -620593257 -10 -322048342 -10 578093727 -10 898998949 -9 -833794004 -9 -704882916 -9 -570204575 -9 -506146571 -9 -109555290 -9 309734100 -9 396668416 -8 -928874025 -8 376566668 -8 596463598 -8 600491164 -8 894775141 -7 -281322833 -7 49984651 -7 154512939 -7 205573228 -7...
output:
3.14159258288778007518 6.28318524821367835505 3.14159261442497865762 3.14159117408144215205 6.28318527029175354472 6.28318529531632778348 3.14159264922942560493 6.28318530367009903071 3.14159264016155836182 6.28318525067592828894 6.28318528164825771364 3.14159275918694019130 3.14159264537055661908 3...
result:
ok 1000 numbers
Test #21:
score: 0
Accepted
time: 24ms
memory: 5536kb
input:
5 23120 8224 -10 -999575056 -10 -997485895 -10 -995458183 -10 -986953157 -10 -985268102 -10 -983223383 -10 -980910524 -10 -980404283 -10 -973605147 -10 -972441960 -10 -972440422 -10 -969122114 -10 -965754004 -10 -964812113 -10 -964558462 -10 -963159275 -10 -962972564 -10 -962085557 -10 -961552443 -1...
output:
3.14159264235138884153 3.14159263124244277987 3.14159260680078263311 3.14159264939531876742 6.28318527220692257243
result:
ok 5 numbers
Test #22:
score: 0
Accepted
time: 21ms
memory: 9372kb
input:
1 99995 60000 1 100001 1 100002 1 100003 1 100004 1 100005 1 100006 1 100007 1 100008 1 100009 1 100010 1 100011 1 100012 1 100013 1 100014 1 100015 1 100016 1 100017 1 100018 1 100019 1 100020 1 100021 1 100022 1 100023 1 100024 1 100025 1 100026 1 100027 1 100028 1 100029 1 100030 1 100031 1 10003...
output:
6.28318530690181795834
result:
ok found '6.2831853', expected '6.2831853', error '0.0000000'
Extra Test:
score: 0
Extra Test Passed