QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#809813#9869. Horizon ScanningTDXIAOWA 43ms8520kbC++202.2kb2024-12-11 17:31:312024-12-11 17:32:01

Judging History

你现在查看的是最新测评结果

  • [2024-12-11 17:32:01]
  • 评测
  • 测评结果:WA
  • 用时:43ms
  • 内存:8520kb
  • [2024-12-11 17:31:31]
  • 提交

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;
}

详细

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'