QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#817199 | #3283. Parallel Lines | SGColin | AC ✓ | 56ms | 3968kb | C++20 | 1.7kb | 2024-12-16 20:53:27 | 2024-12-16 20:53:27 |
Judging History
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'