QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#809813 | #9869. Horizon Scanning | TDXIAO | WA | 43ms | 8520kb | C++20 | 2.2kb | 2024-12-11 17:31:31 | 2024-12-11 17:32:01 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const double pi = acos(-1);
struct Point{
ll x, y;
Point(){}
Point(ll _x, ll _y){x = _x, y=_y;}
};
int operator^(const Point &a, const Point &b){
return a.x * b.y - a.y * b.x;
}
int quad(const Point &a){
if(a.x > 0 && a.y == 0){
return 1;
}else if(a.x > 0 && a.y > 0){
return 2;
}else if(a.x == 0 && a.y > 0){
return 3;
}else if(a.x < 0 && a.y > 0){
return 4;
}else if(a.x < 0 && a.y == 0){
return 5;
}else if(a.x < 0 && a.y < 0){
return 6;
}else if(a.x == 0 && a.y < 0){
return 7;
}else if(a.x > 0 && a.y < 0){
return 8;
}
}
bool cmp(const Point &a, const Point &b){
int qa = quad(a), qb = quad(b);
if(qa != qb){
return qa < qb;
}else{
return (a ^ b) > 0;
}
}
double fun(Point p) {
auto [x, y] = p;
if (x > 0) {
if (y > 0) {
return atan(1.0 * y / x);
} else if (y == 0) {
return 0;
} else {
return 2*pi - atan(1.0 * (-y)/x);
}
} else if (x == 0) {
if (y > 0) {
return pi/2;
} else {
return pi*3/2;
}
} else {
if (y > 0) {
return pi - atan(1.0 * y / (-x));
} else if (y == 0) {
return pi;
} else {
return pi + atan(1.0 * (-y) /(-x));
}
}
}
void solve() {
int n, k;
cin>>n>>k;
vector<Point> a(2*n+1);
for (int i = 1; i <= n; i++) {
ll x, y;
cin>>x>>y;
a[i] = {x, y};
}
sort(a.begin()+1, a.begin()+n+1, cmp);
for (int i = 1; i <= n; i++) {
a[i+n] = a[i];
}
double ans = 0;
for (int i = 1; i <= n; i++) {
double l = fun(a[i]);
double r = fun(a[i+k]);
if (i+k > n) r += 2*pi;
ans = max(ans, r-l);
}
cout<<fixed<<setprecision(20);
cout<<ans<<'\n';
}
int main()
{
if (ifstream("test.in")) {
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
}
ios::sync_with_stdio(false);
cin.tie(0);
int T = 1;
cin>>T;
while (T--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4228kb
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.28318530717958623200 1.57079632679489655800 5.49778714378213795300 3.14159265459155179201 3.14159265358979311600
result:
ok 5 numbers
Test #2:
score: 0
Accepted
time: 26ms
memory: 4164kb
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.69299149748625166190 2.57486343606628764746 4.65275826725351926427 2.77263310738393675692 5.74276580690900217974 4.85769899102039204308 3.41989231259490455983 2.81279996208483895614 6.28318530717958712017 6.28318530717958712017 5.11728076666977305109 6.14678270277863880722 3.84208902353751913239 2...
result:
ok 10000 numbers
Test #3:
score: 0
Accepted
time: 25ms
memory: 4272kb
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.92699081698724139500 6.28318530717958712017 3.36026159946373503828 2.67794504458898696697 3.77038894000522617489 1.76258446878160146554 3.84025247831125593478 5.49778714378213884117 2.03444393579570270703 1.81577498992176078474 4.34718753059651685788 6.14128825257542221294 5.17603658938549582302 5...
result:
ok 10000 numbers
Test #4:
score: 0
Accepted
time: 29ms
memory: 4300kb
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.90978454023457011601 1.97568811307997993509 1.98686083251871936639 3.92699081698724139500 3.69775888371024619161 6.28318530717958712017 6.14128825257542221294 6.19387131418636371905 5.80535425218747125342 6.25289154726081086721 5.72887781097803561181 3.09009184263856750974 1.89254688119153868797 5...
result:
ok 10000 numbers
Test #5:
score: 0
Accepted
time: 26ms
memory: 4200kb
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.23931956094851170036 5.27570524187665856886 5.30039158393225751098 5.38712992260824208302 5.88839418747982534796 4.11731935667914861199 1.13838855122435855804 1.51529782154918013504 6.14765759319408555683 6.15883031263282454404 2.57486343606628675929 5.94016136675888262175 1.60851427926176082650 4...
result:
ok 10000 numbers
Test #6:
score: 0
Accepted
time: 29ms
memory: 4172kb
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.13787529654388297473 6.28318530717958712017 6.11803662976495932213 3.20034847630551588793 2.65375621493014968166 6.25378201897557950417 3.60524026259059926502 3.55981698316902228640 1.50914615615563718620 5.92754942287882613527 6.25879989800686775681 2.62244653934327054401 4.39383330329662236124 5...
result:
ok 10000 numbers
Test #7:
score: 0
Accepted
time: 28ms
memory: 4244kb
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.27130939746127924472 6.28318530717958712017 5.22251472073649836148 6.00306570356891722184 3.92587213546468039027 5.54652899509206953610 3.21031492371172255673 3.03993004992372295447 4.22753178179442556939 3.03201966573687675677 2.19121523381819027776 3.03900809036774077754 4.33132715063550310930 6...
result:
ok 10000 numbers
Test #8:
score: 0
Accepted
time: 29ms
memory: 4256kb
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.58911262874696301850 2.97975522235137013638 0.28379410920832803811 2.03502770689109180324 4.88798114233487002167 1.00406710927139020129 4.74570997626293689109 5.32559632925919856916 4.31027496473292703882 5.60338367941383008741 1.57980509208531305632 4.32964547053911452679 5.54722209679409061778 1...
result:
ok 100 numbers
Test #9:
score: 0
Accepted
time: 34ms
memory: 4436kb
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.91151100390402639562 3.74386851513771201638 2.53848285831534736801 2.15996735885788737619 4.29503770957234465300 4.77167447479618189732 4.68240781260193550395 5.07898439417457403522 1.60080182141066384993 3.34040254563670480081 3.36879252825034924967 2.11301602823006096088 4.85539941013266940217 4...
result:
ok 20 numbers
Test #10:
score: 0
Accepted
time: 43ms
memory: 8452kb
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.85144917898051564187
result:
ok found '0.8514492', expected '0.8514492', error '0.0000000'
Test #11:
score: 0
Accepted
time: 40ms
memory: 7968kb
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.53892668538316623739
result:
ok found '3.5389267', expected '3.5389267', error '0.0000000'
Test #12:
score: 0
Accepted
time: 40ms
memory: 8520kb
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.97202877832588097107
result:
ok found '3.9720288', expected '3.9720288', error '0.0000000'
Test #13:
score: -100
Wrong Answer
time: 40ms
memory: 4304kb
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:
6.17687058931381116622 6.24262665245719894358 2.03604568313005263036 2.85112109249017953161 4.21813246511938455541 3.57047158685250387578 7.09036892902329540789 6.00028743689516552706 2.98757824655085002519 2.80770051303978540602 4.11607797920540008363 6.85486185315705309762 5.19836168674831711201 1...
result:
wrong answer 1st numbers differ - expected: '5.3985251', found: '6.1768706', error = '0.1441774'