QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#811100 | #9869. Horizon Scanning | Nana7# | AC ✓ | 274ms | 7516kb | C++14 | 1.2kb | 2024-12-12 15:27:39 | 2024-12-12 15:27:40 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define I inline
#define double long double
using namespace std;
const double PI = 3.14159265358;
const double eps = 1e-8;
const int N = 200100;
struct point {
int x,y;
}a[N<<1];
char s[N];
int p[N];
int n,m,k;
I double rate(point p1,point p2,int cro) {
double a1=atan2(p1.y,p1.x),a2=atan2(p2.y,p2.x);
//cout<<a1<<' '<<a2<<' '<<cro<<endl;
if(cro) return a2-a1+PI*2;
return a2-a1;
}
I bool cmp(point p1,point p2) {
return atan2(p1.y,p1.x)<atan2(p2.y,p2.x);
}
I void solve() {
cin>>n>>k;
for(int i=1;i<=n;++i) cin>>a[i].x>>a[i].y;
if(n==1) {
cout<< "6.2831853072"<<endl;
return ;
}
sort(a+1,a+1+n,cmp);
for(int i=n+1;i<=n*2;++i) a[i]=a[i-n];
double ans=0;
for(int i=1;i<=n;++i) {
point l=a[i],r=a[i+k];
double rr=rate(l,r,i+k>n);
ans=max(ans,rr);
// cout<<"!!"<<rr<<endl;
}
printf("%.6Lf\n",ans);
//cout<<ans<<endl;
}
int main()
{
int T; cin>>T;
while(T--) {
solve();
}
}
/*
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
*/
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 6376kb
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.2831853072 1.570796 5.497787 3.141593 3.141593
result:
ok 5 numbers
Test #2:
score: 0
Accepted
time: 96ms
memory: 6272kb
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.692991 2.574863 4.652758 2.772633 5.742766 4.857699 3.419892 2.812800 6.283185 6.283185 5.117281 6.146783 3.842089 2.342497 3.463343 6.283185 5.961435 3.324703 5.262775 5.672459 1.673878 1.114191 2.408778 6.283185 5.355890 3.799861 4.193243 4.051346 4.534296 4.361235 1.876019 1.996726 5.553286 3.7...
result:
ok 10000 numbers
Test #3:
score: 0
Accepted
time: 80ms
memory: 4340kb
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.926991 6.283185 3.360262 2.677945 3.770389 1.762584 3.840252 5.497787 2.034444 1.815775 4.347188 6.141288 5.176037 5.465540 5.769039 4.366253 5.994756 4.892242 4.171969 5.677641 5.961435 3.506794 4.542976 5.300392 4.493720 3.141593 6.283185 6.269200 4.680142 5.497787 5.796286 1.290260 4.653633 4.4...
result:
ok 10000 numbers
Test #4:
score: 0
Accepted
time: 95ms
memory: 4332kb
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.909785 1.975688 1.986861 3.926991 3.697759 6.283185 6.141288 6.193871 5.805354 6.252892 5.728878 3.090092 1.892547 5.634190 2.896614 6.283185 2.914794 6.147658 1.951303 5.564355 5.497787 3.098142 4.390638 3.909449 2.641524 6.158830 5.878294 6.283185 3.064821 5.684010 6.283185 2.819842 0.979878 3.0...
result:
ok 10000 numbers
Test #5:
score: 0
Accepted
time: 87ms
memory: 6112kb
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.239320 5.275705 5.300392 5.387130 5.888394 4.117319 1.138389 1.515298 6.147658 6.158830 2.574863 5.940161 1.608514 4.609945 5.071160 4.234558 3.790588 4.037648 3.916002 1.063698 4.280988 5.857256 3.407845 5.421015 2.956245 1.670465 5.869855 4.356753 6.118037 6.180104 1.249046 2.411693 5.421015 6.0...
result:
ok 10000 numbers
Test #6:
score: 0
Accepted
time: 88ms
memory: 6260kb
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.137875 6.283185 6.118037 3.200348 2.653756 6.253782 3.605240 3.559817 1.509146 5.927549 6.258800 2.622447 4.393833 5.497787 4.248741 5.497787 4.629248 3.546484 6.004886 1.196752 2.885441 6.200044 1.923787 5.662936 5.742766 4.514993 3.729595 5.034140 1.692991 4.877538 2.413981 5.001364 1.570796 6.0...
result:
ok 10000 numbers
Test #7:
score: 0
Accepted
time: 90ms
memory: 4220kb
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.271309 6.283185 5.222515 6.003066 3.925872 5.546529 3.210315 3.039930 4.227532 3.032020 2.191215 3.039008 4.331327 6.283185 5.110002 2.946314 5.176037 5.699184 2.061180 6.283185 2.227890 6.170775 6.283185 6.283185 6.282340 2.719334 6.283185 6.283185 2.375282 6.158338 6.273219 5.841466 6.004060 2.2...
result:
ok 10000 numbers
Test #8:
score: 0
Accepted
time: 121ms
memory: 4204kb
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.589113 2.979755 0.283794 2.035028 4.887981 1.004067 4.745710 5.325596 4.310275 5.603384 1.579805 4.329645 5.547222 1.460139 1.531045 2.871675 2.632579 3.124051 0.680521 5.420166 4.778957 2.403035 4.279981 4.678504 4.003763 3.767078 4.582686 1.324022 5.639684 1.882343 3.105245 1.220751 3.858774 4.1...
result:
ok 100 numbers
Test #9:
score: 0
Accepted
time: 139ms
memory: 4216kb
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.911511 3.743869 2.538483 2.159967 4.295038 4.771674 4.682408 5.078984 1.600802 3.340403 3.368793 2.113016 4.855399 4.324001 0.107854 0.179821 5.376655 4.449566 4.394402 2.938185
result:
ok 20 numbers
Test #10:
score: 0
Accepted
time: 186ms
memory: 6828kb
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.851449
result:
ok found '0.8514490', expected '0.8514492', error '0.0000002'
Test #11:
score: 0
Accepted
time: 173ms
memory: 6968kb
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.538927
result:
ok found '3.5389270', expected '3.5389267', error '0.0000001'
Test #12:
score: 0
Accepted
time: 182ms
memory: 6688kb
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.972029
result:
ok found '3.9720290', expected '3.9720288', error '0.0000001'
Test #13:
score: 0
Accepted
time: 124ms
memory: 6264kb
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.398525 5.373908 1.173578 1.544365 3.778289 3.570472 6.282975 5.095925 2.987578 2.305567 3.390784 5.785473 4.810964 0.956757 4.629432 4.799508 4.170289 5.739478 6.121029 3.567468 6.228065 6.282568 4.014655 0.900430 3.994365 5.890522 6.062314 5.785054 6.283185 6.265253 3.373350 1.311523 3.827991 3.4...
result:
ok 10000 numbers
Test #14:
score: 0
Accepted
time: 155ms
memory: 4220kb
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.742802 1.915364 3.804346 1.791916 3.169521 6.078646 3.786067 3.665969 6.226583 5.902152 5.944316 0.715168 3.831574 1.222846 2.598426 5.547329 4.079195 0.704221 5.857822 0.689485 0.937982 1.421523 4.271326 3.118995 6.180969 6.283185 3.898887 4.791446 3.451930 3.838570 6.226893 4.508825 1.484855 0.7...
result:
ok 1000 numbers
Test #15:
score: 0
Accepted
time: 173ms
memory: 6288kb
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.505153 2.712559 5.839679 6.022977 0.461606 0.986991 1.321971 1.925842 5.508608 4.646355 2.287677 2.184873 4.809409 0.477079 0.556342 1.093619 5.182715 3.113185 4.380234 2.749259 2.791795 6.271733 5.753875 2.900719 2.639328 1.252679 3.074636 5.940092 4.173466 1.516478 1.227927 3.555271 6.267308 6.2...
result:
ok 100 numbers
Test #16:
score: 0
Accepted
time: 195ms
memory: 6280kb
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.417080 6.161192 3.960020 3.994362 2.551551 0.522724 4.097844 6.210383 5.981728 0.777224
result:
ok 10 numbers
Test #17:
score: 0
Accepted
time: 155ms
memory: 6896kb
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.442594
result:
ok found '5.4425940', expected '5.4425939', error '0.0000000'
Test #18:
score: 0
Accepted
time: 225ms
memory: 6820kb
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.642475
result:
ok found '0.6424750', expected '0.6424746', error '0.0000004'
Test #19:
score: 0
Accepted
time: 274ms
memory: 7516kb
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.401246
result:
ok found '4.4012460', expected '4.4012457', error '0.0000001'
Test #20:
score: 0
Accepted
time: 103ms
memory: 6208kb
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.141593 6.283185 3.141593 3.141591 6.283185 6.283185 3.141593 6.283185 3.141593 6.283185 6.283185 3.141593 3.141593 3.141593 3.141593 6.283185 3.141593 3.141593 3.141593 6.283185 6.283185 3.141593 3.141593 3.141593 3.141593 3.141593 6.283185 3.141593 3.141593 6.283185 3.141593 3.141593 6.283185 6.2...
result:
ok 1000 numbers
Test #21:
score: 0
Accepted
time: 123ms
memory: 6312kb
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.141593 3.141593 3.141593 3.141593 6.283185
result:
ok 5 numbers
Test #22:
score: 0
Accepted
time: 81ms
memory: 6996kb
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.283185
result:
ok found '6.2831850', expected '6.2831853', error '0.0000000'
Extra Test:
score: 0
Extra Test Passed