QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#424868#3283. Parallel LinesNYCU_template#AC ✓659ms3700kbC++201.3kb2024-05-29 19:13:152024-05-29 19:13:15

Judging History

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

  • [2024-05-29 19:13:15]
  • 评测
  • 测评结果:AC
  • 用时:659ms
  • 内存:3700kb
  • [2024-05-29 19:13:15]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
using Slope = pair<ll, ll>;
const int M = 20;
map<Slope, int> cnt;
bool match[M];
ll m, x[M], y[M];
ll ans;
void DFS(int level) {
    if(level == m) {
        ll res = 0;
        for(auto P : cnt) {
            res += (P.second * (P.second - 1)) / 2;
        }
        ans = max(res, ans);
        return;
    }

    if(match[level]) {
        DFS(level + 1);
        return;
    }

    for(int i = level + 1; i < m; i++) {
        if(match[i]) continue;

        match[i] = true;
        match[level] = true;
        ll dif_x = x[level] - x[i];
        ll dif_y = y[level] - y[i];

        if(dif_x < 0) {
            dif_x *= -1;
            dif_y *= -1;
        }

        if(dif_x == 0) {
            dif_y = 1;
        } else {
            ll gd = __gcd(dif_x, dif_y);
            dif_x /= gd;
            dif_y /= gd;
        }

        cnt[{dif_x, dif_y}]++;
        DFS(level + 1);

        cnt[{dif_x, dif_y}]--;

        if(cnt[{dif_x, dif_y}] == 0) {
            cnt.erase({dif_x, dif_y});
        }
        match[i] = false;
        match[level] = false;
    }
}
int main() {
    cin >> m;
    for(int i = 0; i < m; i++) {
        cin >> x[i] >> y[i];
    }

    DFS(0);

    cout << ans << "\n";
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3692kb

input:

6
0 0
0 5
3 -2
3 5
5 0
5 7

output:

3

result:

ok single line: '3'

Test #2:

score: 0
Accepted
time: 631ms
memory: 3636kb

input:

16
512 -867
198 -615
134 -269
587 691
-303 -57
708 937
411 354
-724 108
628 897
553 657
356 -536
671 906
342 285
658 -794
-754 93
675 910

output:

9

result:

ok single line: '9'

Test #3:

score: 0
Accepted
time: 639ms
memory: 3632kb

input:

16
955 -856
815 -179
988 -823
-209 39
934 -533
-686 -437
-850 -213
372 -612
867 -600
-990 960
372 -522
-768 -970
-205 43
-990 987
-850 -301
815 -269

output:

9

result:

ok single line: '9'

Test #4:

score: 0
Accepted
time: 625ms
memory: 3632kb

input:

16
726 502
905 -385
484 371
889 324
182 -312
200 -120
808 502
457 18
304 -184
317 -184
-565 345
565 371
116 -120
821 -469
-580 330
877 312

output:

9

result:

ok single line: '9'

Test #5:

score: 0
Accepted
time: 636ms
memory: 3632kb

input:

16
-67 -723
254 963
213 -578
-412 -335
-212 -235
191 -589
-981 219
-202 210
242 -720
-989 215
-168 3
-206 -16
-137 -758
201 804
-324 149
-302 856

output:

15

result:

ok single line: '15'

Test #6:

score: 0
Accepted
time: 620ms
memory: 3632kb

input:

16
162 571
-699 -559
645 507
-976 633
519 320
-822 710
70 525
317 -829
694 -832
408 -782
-867 -643
784 -787
356 -808
569 470
221 -877
529 449

output:

21

result:

ok single line: '21'

Test #7:

score: 0
Accepted
time: 633ms
memory: 3640kb

input:

16
-805 -254
-989 521
-232 -357
-517 -40
483 916
681 659
916 706
-879 543
-200 -350
203 -270
-792 -95
-12 817
145 162
155 164
85 -293
-515 -196

output:

28

result:

ok single line: '28'

Test #8:

score: 0
Accepted
time: 634ms
memory: 3612kb

input:

16
342 -60
142 -165
356 -536
585 -429
528 256
723 691
691 910
353 -569
553 657
134 -269
411 354
512 -867
340 -724
348 -636
671 906
485 -303

output:

4

result:

ok single line: '4'

Test #9:

score: 0
Accepted
time: 632ms
memory: 3640kb

input:

16
-433 788
238 -612
-291 961
-381 -6
805 982
-761 252
-808 -265
602 253
-954 618
823 -420
687 270
-487 464
-789 651
468 -491
-303 462
259 -381

output:

5

result:

ok single line: '5'

Test #10:

score: 0
Accepted
time: 639ms
memory: 3684kb

input:

16
-560 823
-374 -972
116 555
934 443
-325 -972
-603 -803
-560 877
553 -565
901 443
-226 796
553 -473
-927 889
-927 957
126 555
-672 -803
-226 867

output:

12

result:

ok single line: '12'

Test #11:

score: 0
Accepted
time: 648ms
memory: 3628kb

input:

16
553 -473
-672 -803
116 555
553 -565
-374 -972
126 555
901 443
-560 877
-927 889
-226 867
-614 823
-832 788
-297 796
-603 -803
-374 -923
934 443

output:

5

result:

ok single line: '5'

Test #12:

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

input:

8
0 0
0 5
2 2
2 7
3 -2
5 0
4 -2
8 2

output:

6

result:

ok single line: '6'

Test #13:

score: 0
Accepted
time: 586ms
memory: 3644kb

input:

16
0 0
0 1
100 2
100 4
200 15
200 18
300 43
300 49
50 0
70 1
-123 -93
-122 -93
150 52
151 55
-571 -432
-570 -431

output:

7

result:

ok single line: '7'

Test #14:

score: 0
Accepted
time: 585ms
memory: 3632kb

input:

16
0 0
1 0
2 100
4 100
15 200
18 200
43 300
49 300
0 50
1 70
-93 -123
-93 -122
52 150
55 151
-432 -571
-431 -570

output:

7

result:

ok single line: '7'

Test #15:

score: 0
Accepted
time: 586ms
memory: 3636kb

input:

16
2 1
3 3
5 2
6 4
8 5
9 7
111 6
112 8
114 5
108 12
16 11
17 10
0 10
101 7
104 6
13 0

output:

7

result:

ok single line: '7'

Test #16:

score: 0
Accepted
time: 659ms
memory: 3584kb

input:

16
1 2
3 3
2 5
4 6
5 8
7 9
6 111
8 112
5 114
12 108
11 16
10 17
10 0
7 101
6 104
0 13

output:

7

result:

ok single line: '7'

Test #17:

score: 0
Accepted
time: 619ms
memory: 3648kb

input:

16
0 0
20 0
3 1
23 1
-3 3
12 16
16 6
7 7
27 7
10 8
30 8
25 11
2 12
1 14
11 116
5 118

output:

7

result:

ok single line: '7'

Test #18:

score: 0
Accepted
time: 603ms
memory: 3568kb

input:

16
0 0
20 0
3 1
23 1
-3 3
15 10
16 6
7 7
27 7
10 8
30 8
25 11
2 12
1 14
11 16
5 18

output:

11

result:

ok single line: '11'

Test #19:

score: 0
Accepted
time: 635ms
memory: 3684kb

input:

16
0 0
0 20
1 3
1 23
3 -3
10 15
6 16
7 7
7 27
8 10
8 30
11 25
12 2
14 1
16 11
18 5

output:

11

result:

ok single line: '11'

Test #20:

score: 0
Accepted
time: 578ms
memory: 3696kb

input:

16
0 0
0 20
1 3
1 23
3 -3
16 12
6 16
7 7
7 27
8 10
8 30
11 25
12 2
14 1
116 11
118 5

output:

7

result:

ok single line: '7'

Test #21:

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

input:

4
2 2
1 0
1 1
0 1

output:

0

result:

ok single line: '0'

Test #22:

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

input:

10
0 0
0 3
4 0
4 4
8 2
8 7
1 2
6 -2
9 3
10 9

output:

4

result:

ok single line: '4'

Test #23:

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

input:

10
0 0
3 0
0 4
4 4
2 8
7 8
2 1
-2 6
3 9
9 10

output:

4

result:

ok single line: '4'

Test #24:

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

input:

10
0 0
4 4
3 2
6 -1
7 5
8 2
4 0
8 9
9 3
0 4

output:

4

result:

ok single line: '4'

Test #25:

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

input:

10
0 0
4 4
2 3
-1 6
5 7
2 8
0 4
9 8
3 9
4 0

output:

4

result:

ok single line: '4'

Test #26:

score: 0
Accepted
time: 38ms
memory: 3636kb

input:

14
0 0
-2 2
5 -1
3 1
0 3
3 6
4 3
4 11
6 5
6 13
100 11
102 5
102 13
103 6

output:

11

result:

ok single line: '11'

Test #27:

score: 0
Accepted
time: 40ms
memory: 3688kb

input:

14
0 0
2 -2
-1 5
1 3
3 0
6 3
3 4
11 4
5 6
13 6
11 100
5 102
13 102
6 103

output:

11

result:

ok single line: '11'

Test #28:

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

input:

2
-1000 1000
1000 -1000

output:

0

result:

ok single line: '0'

Test #29:

score: 0
Accepted
time: 640ms
memory: 3564kb

input:

16
327 449
-509 761
-553 515
360 948
147 877
-694 468
241 320
463 -753
-206 -991
473 -738
-156 -916
-215 54
-112 -476
-452 780
-18 -335
-146 77

output:

12

result:

ok single line: '12'

Test #30:

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

input:

10
553 657
-39 -615
356 -536
587 759
411 354
342 147
675 918
512 -867
671 906
877 -794

output:

4

result:

ok single line: '4'

Test #31:

score: 0
Accepted
time: 4ms
memory: 3700kb

input:

12
356 -536
342 147
-39 -615
877 -794
411 354
587 759
628 897
671 906
553 657
675 918
512 -867
340 -724

output:

4

result:

ok single line: '4'

Test #32:

score: 0
Accepted
time: 40ms
memory: 3572kb

input:

14
553 657
342 147
356 -536
628 897
671 906
340 -724
-39 -615
877 -794
512 -867
587 759
411 354
108 485
-303 -57
675 918

output:

4

result:

ok single line: '4'