QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#376771#2165. Ley Lineswillow#AC ✓4040ms4344kbC++172.4kb2024-04-04 16:27:562024-04-04 16:27:56

Judging History

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

  • [2024-04-04 16:27:56]
  • 评测
  • 测评结果:AC
  • 用时:4040ms
  • 内存:4344kb
  • [2024-04-04 16:27:56]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef long double LD;
const int MAXN = 3005;
const LD PI = acosl(-1.0);
const LD eps = 1e-7;

struct Point {
    LL x, y;
    Point(LL x = 0, LL y = 0) : x(x), y(y) {}
    Point operator + (const Point &rhs) const {
        return Point(x + rhs.x, y + rhs.y);
    }
    Point operator - (const Point &rhs) const {
        return Point(x - rhs.x, y - rhs.y);
    }
    LL operator * (const Point &rhs) const {
        return x * rhs.x + y * rhs.y;
    }
    LL operator ^ (const Point &rhs) const {
        return x * rhs.y - y * rhs.x;
    }
    Point operator * (const double &k) const {
        return Point(x * k, y * k);
    }
    Point operator / (const double &k) const {
        return Point(x / k, y / k);
    }
    LL len2() {
        return x * x + y * y;
    }
    double len() {
        return sqrt(len2());
    }
    Point Unit() {
        return *this / len();
    }
} p[MAXN];

int n, ans;
LL t, t2;
pair<LD, int> a[MAXN * 8]; int tot = 0;

void Add(LD l, LD r) {
    while (r < -PI) {
        l += PI * 2;
        r += PI * 2;
    }
//cerr << l << ' ' << r << endl;
    if (l < -PI) {
        a[++tot] = make_pair(l + PI * 2, 1);
        a[++tot] = make_pair(PI, -1);
        a[++tot] = make_pair(-PI, 1);
        a[++tot] = make_pair(r, -1);
    } else {
        a[++tot] = make_pair(l, 1);
        a[++tot] = make_pair(r, -1);
    }
}

void Work(int k) {
//cerr << "solve " << k << endl;
    tot = 0;
    for (int i = 1; i <= n; ++i) {
        //cerr << "cover " << i << endl;
        if (i == k) continue;
        LL len2 = (p[i] - p[k]).len2();
        LD l, r = atan2l(p[i].y - p[k].y, p[i].x - p[k].x);
        if (t2 >= len2) {
            Add(r - PI, r);
        } else {
            LD cur = asinl(t / sqrtl(len2));
            Add(r - cur, r);
            Add(r - PI, r - PI + cur);
        }
    }
    sort(a + 1, a + tot + 1);
    int cnt = 0;
    for (int i = 1; i <= tot; ++i) {
        cnt += a[i].second;
        ans = max(ans, cnt + 1);
    }
//cerr << "ans " << ans << endl;
}

void solve() {
    scanf("%d %lld", &n, &t);
    t2 = t * t;
    for (int i = 1; i <= n; ++i) {
        scanf("%lld %lld", &p[i].x, &p[i].y);
    }
    ans = 0;
    for (int i = 1; i <= n; ++i) {
        Work(i);
    }
    printf("%d\n", ans);
}

int main() {
    solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1815ms
memory: 4108kb

input:

2000 5000000
138090446 103566751
348232749 261174765
49768701 37325003
46543152 34908666
163731761 122797611
180801649 135599821
37619795 28211762
121510800 91131600
221124078 165843225
163300901 122476127
265149423 198860868
291091848 218320087
233241323 174929208
285406437 214055522
16753835 12563...

output:

2000

result:

ok single line: '2000'

Test #2:

score: 0
Accepted
time: 4040ms
memory: 4328kb

input:

3000 1000
972962303 -722488325
-136831928 755587524
-114943014 -765971883
942873013 -96259977
-756167306 -844842778
41690945 -998523447
-341222029 -292637433
-765737678 -51096465
969741938 -758945887
167296994 26527628
904728280 -892381891
914702231 247851872
-505519868 570685484
202269268 46911080
...

output:

4

result:

ok single line: '4'

Test #3:

score: 0
Accepted
time: 1ms
memory: 3800kb

input:

5 9
15 5
-7 -3
11 13
-1 9
0 0

output:

4

result:

ok single line: '4'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3944kb

input:

4 25
0 -11
-27 -14
10 39
-24 14

output:

3

result:

ok single line: '3'

Test #5:

score: 0
Accepted
time: 1ms
memory: 3940kb

input:

4 100000001
0 0
500000000 0
0 100000000
500000000 100000000

output:

4

result:

ok single line: '4'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3860kb

input:

4 100000001
0 0
0 500000000
100000000 0
100000000 500000000

output:

4

result:

ok single line: '4'

Test #7:

score: 0
Accepted
time: 1ms
memory: 3840kb

input:

10 18
-22 56
84 -15
-72 95
-83 76
-41 71
-43 19
-37 -25
9 17
-67 -44
-79 -43

output:

5

result:

ok single line: '5'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3864kb

input:

10 17
-22 56
84 -15
-72 95
-83 76
-41 71
-43 19
-37 -25
9 17
-67 -44
-79 -43

output:

4

result:

ok single line: '4'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3904kb

input:

20 1588
600 -6
751 931
890 -727
8 113
196 289
865 808
196 337
-313 218
288 -101
966 280
-312 -880
-607 -539
165 -521
-258 175
-632 893
464 525
-114 215
455 -668
45 -981
446 -760

output:

20

result:

ok single line: '20'

Test #10:

score: 0
Accepted
time: 1ms
memory: 3904kb

input:

20 1587
600 -6
751 931
890 -727
8 113
196 289
865 808
196 337
-313 218
288 -101
966 280
-312 -880
-607 -539
165 -521
-258 175
-632 893
464 525
-114 215
455 -668
45 -981
446 -760

output:

19

result:

ok single line: '19'

Test #11:

score: 0
Accepted
time: 1ms
memory: 3792kb

input:

20 2
685 -462
-149 -71
157 -363
-457 -912
-830 222
642 -974
-985 -126
-168 -588
-271 764
-74 -163
287 957
126 114
-708 -698
-739 -323
695 -807
-787 -63
-711 -379
866 446
258 966
91 -15

output:

3

result:

ok single line: '3'

Test #12:

score: 0
Accepted
time: 1ms
memory: 3836kb

input:

20 1
685 -462
-149 -71
157 -363
-457 -912
-830 222
642 -974
-985 -126
-168 -588
-271 764
-74 -163
287 957
126 114
-708 -698
-739 -323
695 -807
-787 -63
-711 -379
866 446
258 966
91 -15

output:

2

result:

ok single line: '2'

Test #13:

score: 0
Accepted
time: 15ms
memory: 3956kb

input:

200 17111108
91744676 673796098
-100893260 56552744
-719994 -693651886
-727727944 213414651
929784607 -484802952
190353490 -914184609
-621686549 -704818183
-364325628 745493628
57709812 577602650
924875154 -117737487
-543513921 -248518268
487019621 810219465
568981672 861955195
-332677198 249115376
...

output:

10

result:

ok single line: '10'

Test #14:

score: 0
Accepted
time: 15ms
memory: 3928kb

input:

200 17111107
91744676 673796098
-100893260 56552744
-719994 -693651886
-727727944 213414651
929784607 -484802952
190353490 -914184609
-621686549 -704818183
-364325628 745493628
57709812 577602650
924875154 -117737487
-543513921 -248518268
487019621 810219465
568981672 861955195
-332677198 249115376
...

output:

9

result:

ok single line: '9'

Test #15:

score: 0
Accepted
time: 16ms
memory: 3824kb

input:

200 246869895
390618629 -512123632
506481914 -177341723
-590696703 -815495250
893234336 -677056123
-315183449 -612271667
373779191 83003347
-776511418 719272647
-686891146 973715411
-243682185 -258111730
848736614 -173604499
-685559629 -866633992
-780459525 827857604
-554191139 213701528
-657195418 ...

output:

50

result:

ok single line: '50'

Test #16:

score: 0
Accepted
time: 10ms
memory: 3956kb

input:

200 181677460
4135408 -4993852
96991106 -78149271
37479480 26347800
-51818964 56474965
-47591791 55690373
70525034 -45337580
-36817810 -41715138
79403024 -99964985
39192770 5018744
1838651 -31267289
80815523 37820882
28109580 -25662118
93413214 -99805829
-40897297 29137388
-45872755 29320300
1173478...

output:

189

result:

ok single line: '189'

Test #17:

score: 0
Accepted
time: 1717ms
memory: 4136kb

input:

2000 2
-343182613 -998903347
-527075600 941044621
56376084 290968868
-708953076 844361128
-981539598 18820430
196665093 -932442670
-357714908 896607629
-457198184 409846326
-859985382 415440860
79978773 -295757862
-477206933 504924896
179251229 764623154
159929816 531652490
404223501 -927223084
-659...

output:

3

result:

ok single line: '3'

Test #18:

score: 0
Accepted
time: 1720ms
memory: 4156kb

input:

2000 1
-343182613 -998903347
-527075600 941044621
56376084 290968868
-708953076 844361128
-981539598 18820430
196665093 -932442670
-357714908 896607629
-457198184 409846326
-859985382 415440860
79978773 -295757862
-477206933 504924896
179251229 764623154
159929816 531652490
404223501 -927223084
-659...

output:

2

result:

ok single line: '2'

Test #19:

score: 0
Accepted
time: 1748ms
memory: 4148kb

input:

2000 633
-580519085 -258767603
617956170 975429291
396417286 -145369820
292961126 192246821
971467239 119922346
787864825 989697461
172405625 -170330345
891216851 -868040762
625166572 618490292
-654380255 477668361
-361369794 -808302475
-783181335 -740950694
287601240 354061526
952148062 -856273114
...

output:

4

result:

ok single line: '4'

Test #20:

score: 0
Accepted
time: 1738ms
memory: 4156kb

input:

2000 489384
-890986730 620722701
187125954 -492102569
-828037905 320373875
-14319108 -258697727
-530197468 291324989
795408325 251303602
-51872290 999429189
-215414352 -969351881
997215020 -979399877
817007088 -269736109
-227566544 898254941
-372688013 30018439
-317510501 -793683852
-776167110 -4656...

output:

10

result:

ok single line: '10'

Test #21:

score: 0
Accepted
time: 1737ms
memory: 4152kb

input:

2000 489383
-890986730 620722701
187125954 -492102569
-828037905 320373875
-14319108 -258697727
-530197468 291324989
795408325 251303602
-51872290 999429189
-215414352 -969351881
997215020 -979399877
817007088 -269736109
-227566544 898254941
-372688013 30018439
-317510501 -793683852
-776167110 -4656...

output:

9

result:

ok single line: '9'

Test #22:

score: 0
Accepted
time: 1799ms
memory: 4196kb

input:

2000 41608331
-119320741 440098920
-235197525 197375424
-962515849 796819926
762993775 -690399505
129074435 475146930
825646618 -470210346
-261851586 -877912412
846563656 19656954
-747085266 -403450740
-913458607 92840027
-987259735 -593584926
79828018 841551160
-895490531 254623776
-306986911 -9686...

output:

100

result:

ok single line: '100'

Test #23:

score: 0
Accepted
time: 1800ms
memory: 4192kb

input:

2000 41608330
-119320741 440098920
-235197525 197375424
-962515849 796819926
762993775 -690399505
129074435 475146930
825646618 -470210346
-261851586 -877912412
846563656 19656954
-747085266 -403450740
-913458607 92840027
-987259735 -593584926
79828018 841551160
-895490531 254623776
-306986911 -9686...

output:

99

result:

ok single line: '99'

Test #24:

score: 0
Accepted
time: 1095ms
memory: 4072kb

input:

2000 199727479
-53223126 -55818245
-92129485 -19199688
58856831 88570222
86169042 -95399224
367061 -48460890
58170084 -36320898
93450227 43532455
37644677 98811583
-75184478 -30881716
-8192069 46263658
42095990 -52276462
-7519787 33000198
-43826790 84533295
-68819157 58201823
-62447226 2017392
-4653...

output:

2000

result:

ok single line: '2000'

Test #25:

score: 0
Accepted
time: 1088ms
memory: 4216kb

input:

2000 199727478
-53223126 -55818245
-92129485 -19199688
58856831 88570222
86169042 -95399224
367061 -48460890
58170084 -36320898
93450227 43532455
37644677 98811583
-75184478 -30881716
-8192069 46263658
42095990 -52276462
-7519787 33000198
-43826790 84533295
-68819157 58201823
-62447226 2017392
-4653...

output:

1999

result:

ok single line: '1999'

Test #26:

score: 0
Accepted
time: 1831ms
memory: 4088kb

input:

2000 5000000
184722003 144791021
93952800 76713160
355565810 272922752
10080903 7560348
161532873 121150232
83380382 68784902
244085319 183065312
271813160 210108825
142893104 107167937
353073831 271053394
210509096 164132522
227593811 170694660
151655572 119992447
94076056 76807550
171996011 128998...

output:

1062

result:

ok single line: '1062'

Test #27:

score: 0
Accepted
time: 1834ms
memory: 4044kb

input:

2000 5000000
184722003 144791021
90952800 80713160
358565810 268922752
4080903 15560348
161532873 121150232
80380382 72784902
238085319 191065312
271813160 210108825
142893104 107167937
353073831 271053394
213509096 160132522
221593811 178694660
148655572 123992447
94076056 76807550
165996011 136998...

output:

719

result:

ok single line: '719'

Test #28:

score: 0
Accepted
time: 1827ms
memory: 4084kb

input:

2000 5000000
178722003 152791021
93952800 76713160
355565810 272922752
4080903 15560348
161532873 121150232
77380382 76784902
238085319 191065312
265813160 218108825
136893104 115167937
353073831 271053394
210509096 164132522
227593811 170694660
145655572 127992447
88076056 84807550
165996011 136998...

output:

550

result:

ok single line: '550'

Test #29:

score: 0
Accepted
time: 1053ms
memory: 4040kb

input:

2000 1000000000
270216262 191391529
-71873449 301950427
-150959365 -58395080
-192573491 317442754
182095963 211082011
-191715342 201886571
-198986803 -269896375
267998018 287998487
-365464781 114316400
-65098851 163821529
-353046213 182909373
-180484601 -318649346
-42517839 97905455
106757930 140807...

output:

2000

result:

ok single line: '2000'

Test #30:

score: 0
Accepted
time: 3980ms
memory: 4344kb

input:

3000 1
266881498 -221446858
-983460357 -393410634
-703209466 367142771
-8342164 663902846
755649943 -789495720
-415167281 -987245734
664447884 -765540949
-181798933 575677791
-833162733 -714141924
557238940 -332077929
992470725 -809717762
789066529 341930258
-847367656 243540285
640049353 -569023132...

output:

3

result:

ok single line: '3'

Test #31:

score: 0
Accepted
time: 4025ms
memory: 4172kb

input:

3000 3
900832172 -606705
-304780790 -695962
143418655 -546393
312299509 38072
405127874 592140
985268335 444466
-661295659 911660
671837103 -814455
-916482963 250649
-760247290 28452
58877299 722871
249123771 911091
-699048864 -110057
279317304 380110
-611847327 887707
-28653638 -909161
259134502 -6...

output:

4

result:

ok single line: '4'

Test #32:

score: 0
Accepted
time: 3575ms
memory: 4260kb

input:

3000 1000000000
-558015837 955631234
-314205785 888290696
-301559731 685297365
-995023179 944708708
302745131 -990986150
514628703 145951842
-970510495 680616486
-405130105 504546343
-579809713 196337402
943332394 376770792
535025961 -75905168
-644549144 -327639591
-212615984 -658232533
-967392406 -...

output:

1784

result:

ok single line: '1784'

Test #33:

score: 0
Accepted
time: 4005ms
memory: 4164kb

input:

3000 4
-440803 -72149196
-977832 138772735
-267665 273278403
874639 -286860353
-672663 -707590450
-957361 -836719239
295855 -503392925
-657996 -67364290
775927 676787063
-822928 -415377170
728781 -592803919
61118 543404588
244312 690983314
-238381 804458734
-216646 234635287
-782846 -34848426
430746...

output:

4

result:

ok single line: '4'