QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#817199#3283. Parallel LinesSGColinAC ✓56ms3968kbC++201.7kb2024-12-16 20:53:272024-12-16 20:53:27

Judging History

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

  • [2024-12-16 20:53:27]
  • 评测
  • 测评结果:AC
  • 用时:56ms
  • 内存:3968kb
  • [2024-12-16 20:53:27]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define N 17
#define M 1007 
#define fr first
#define sc second

map<pii, int> f;

int gcd(int a, int b) {return b ? gcd(b, a % b) : a;}

pii operator - (const pii &a, const pii &b) {return {a.fr - b.fr, a.sc - b.sc};}
pii operator / (const pii &a, const int &k) {return {a.fr / k, a.sc / k};}

pii a[N];

bool vis[N];

int s[N][N], cnt[M];

int n, idcnt, ans, res;

inline int c2(int x) {return x * (x - 1) / 2;}

inline void add(int x) {res -= c2(cnt[x]); ++cnt[x]; res += c2(cnt[x]);}

inline void del(int x) {res -= c2(cnt[x]); --cnt[x]; res += c2(cnt[x]);}

// (m - 1)!! = 2027025 
void dfs(int p) {
    if (p == n / 2) {ans = max(ans, res); return;}
    int A = 0;
    for (int i = 1; i <= n; ++i) 
        if (!vis[i]) {vis[i] = true; A = i; break;}
    for (int i = A + 1; i <= n; ++i)
        if (!vis[i]) {
            vis[i] = true; add(s[A][i]); dfs(p + 1);
            vis[i] = false; del(s[A][i]);
        }
    vis[A] = false;
}

int main() {
    n = rd();
    for (int i = 1; i <= n; ++i) {a[i].fr = rd(); a[i].sc = rd();}
    for (int i = 1; i <= n; ++i)
        for (int j = i + 1; j <= n; ++j) {
            pii tmp = (a[i] < a[j] ? a[j] - a[i] : a[i] - a[j]);
            tmp = tmp / gcd(abs(tmp.fr), abs(tmp.sc));
            if (!f[tmp]) f[tmp] = ++idcnt;
            s[i][j] = f[tmp];
        }
    dfs(0);
    printf("%d\n", ans);
    return 0;
}

详细

Test #1:

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

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: 55ms
memory: 3768kb

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: 55ms
memory: 3848kb

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: 55ms
memory: 3840kb

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: 55ms
memory: 3848kb

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: 55ms
memory: 3896kb

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: 55ms
memory: 3840kb

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: 55ms
memory: 3836kb

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: 51ms
memory: 3852kb

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: 55ms
memory: 3848kb

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: 56ms
memory: 3840kb

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: 3836kb

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: 55ms
memory: 3768kb

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: 55ms
memory: 3968kb

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: 55ms
memory: 3812kb

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: 55ms
memory: 3788kb

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: 55ms
memory: 3776kb

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: 55ms
memory: 3796kb

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: 56ms
memory: 3768kb

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: 56ms
memory: 3776kb

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: 3784kb

input:

4
2 2
1 0
1 1
0 1

output:

0

result:

ok single line: '0'

Test #22:

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

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: 0ms
memory: 3900kb

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: 0ms
memory: 3776kb

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: 0ms
memory: 3764kb

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: 2ms
memory: 3848kb

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: 4ms
memory: 3852kb

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: 3828kb

input:

2
-1000 1000
1000 -1000

output:

0

result:

ok single line: '0'

Test #29:

score: 0
Accepted
time: 56ms
memory: 3788kb

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: 0ms
memory: 3828kb

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: 1ms
memory: 3784kb

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: 4ms
memory: 3852kb

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'