QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#190788 | #1945. Finding Polly | SolitaryDream | AC ✓ | 2154ms | 8700kb | C++14 | 4.2kb | 2023-09-29 14:16:33 | 2023-09-29 14:16:33 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,s,t) for(int i=(s),_t=(t); i<=_t; ++i)
typedef long long ll;
typedef long double db;
struct frac {
__int128 u,d;
frac(__int128 u_=0,__int128 d_=1) {
u=u_,d=d_;
// __int128 g=__gcd(u,d);
// u/=g,d/=g;
if(d<0) u=-u,d=-d;
}
bool operator <(const frac &s) const{
return (__int128)u*s.d<(__int128)s.u*d;
}
bool operator <=(const frac &s) const{
return (__int128)u*s.d<=(__int128)s.u*d;
}
frac operator +(const frac &s) const{
__int128 g=__gcd(d,s.d);
return frac(u*(s.d/g)+s.u*(d/g),d/g*s.d);
}
frac operator -(const frac &s) const{
__int128 g=__gcd(d,s.d);
return frac(u*(s.d/g)-s.u*(d/g),d/g*s.d);
}
frac operator *(const frac &s) const{
return frac(u*s.u,d*s.d);
}
frac operator /(const frac &s) const{
return frac(u*s.d,d*s.u);
}
};
int sgn(frac x) {
return x.u<0?-1:x.u>0;
}
struct Point {
frac x,y;
Point operator -(const Point &s) const{
return {x-s.x,y-s.y};
}
Point operator +(const Point &s) const{
return {x+s.x,y+s.y};
}
Point operator *(const frac &s) const{
return {x*s,y*s};
}
bool zero() const {
return !x.u&&!y.u;
}
};
frac det(Point a,Point b) {
return a.x*b.y-a.y*b.x;
}
frac dot(Point a,Point b) {
return a.x*b.x+a.y*b.y;
}
const int N=13;
Point a[N],b[N];
vector<Point> f[N][N];
bool g[N][N][N][N];
bool q[N][N][N][N][N][N];
bool o[N][N][N][N][N];
vector<Point> intersection(Point a,Point b,Point c,Point d) {
if(det(a-b,c-d).u==0) return {};
return {a+(b-a)*(det(d-c,a-c)/det(b-a,d-c))};
}
bool check(Point a,Point b,Point c,Point d) {
return sgn(det(b-a,c-a))*sgn(det(b-a,d-a))==-1 && sgn(det(d-c,a-c))*sgn(det(d-c,b-c))==-1;
}
bool on_segment(Point a,Point b,Point c) {
return sgn(det(a-b,a-c))==0 && sgn(dot(c-a,c-b))<0;
}
int res=0;
bool vis[N];
int w[N];
int n;
void dfs(int p) {
// if(p==4 && w[4]==4) cerr << " -- " << endl;
FOR(i,1,p-2) if(!g[w[i]][w[i+1]][w[p-1]][w[p]]) return ;
FOR(i,1,p-2) if(!o[w[i]][w[i+1]][w[p-1]][w[p-2]][w[p]]) return ;
FOR(i,2,p-2) if(!o[w[p-1]][w[p]][w[i]][w[i-1]][w[i+1]]) return ;
FOR(i,2,p-2) if(!q[w[i]][w[i-1]][w[i+1]][w[p-1]][w[p-2]][w[p]]) return ;
if(p==n) {
FOR(i,1,p-1) if(!g[w[i]][w[i+1]][w[p]][w[1]]) return ;
FOR(i,1,p-1) if(!o[w[i]][w[i+1]][w[p]][w[1]][w[p-1]]) return ;
FOR(i,1,p-1) if(!o[w[i]][w[i+1]][w[1]][w[p]][w[2]]) return ;
FOR(i,2,p-1) if(!o[w[p]][w[1]][w[i]][w[i-1]][w[i+1]]) return ;
FOR(i,2,p-1) if(!q[w[i]][w[i-1]][w[i+1]][w[p]][w[1]][w[p-1]]) return ;
FOR(i,2,p-1) if(!q[w[i]][w[i-1]][w[i+1]][w[1]][w[p]][w[2]]) return ;
// FOR(i,1,p) cerr << w[i] << " \n"[i==p];
++res;
return ;
}
++p;
FOR(i,1,n) if(!vis[i]) {
vis[i]=1;
w[p]=i;
dfs(p);
vis[i]=0;
}
}
int main() {
// int x=time(NULL);
// cerr<<x<<endl;
// // auto x=1695910213;
// srand(x);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(12);
cin >> n;
FOR(i,1,n)
{
int u,v,w,x;
cin>>u>>v>>w>>x;
a[i].x.u=u,a[i].y.u=v;
b[i].x.u=w,b[i].y.u=x;
}
FOR(i,1,n) FOR(j,1,n) if(i!=j) f[i][j]=intersection(a[i],b[i],a[j],b[j]);
FOR(i,1,n) FOR(j,1,n) if(f[i][j].size()) {
FOR(k,1,n) FOR(h,1,n) if(f[k][h].size()) {
g[i][j][k][h]=!(f[i][j][0]-f[k][h][0]).zero();
}
}
FOR(i,1,n) FOR(j,1,n) FOR(k,1,n) if(g[i][j][i][k]) {
FOR(h,1,n) FOR(u,1,n) FOR(v,1,n) if(g[h][u][h][v]) {
q[i][j][k][h][u][v]=!check(f[i][j][0],f[i][k][0],f[h][u][0],f[h][v][0]);
}
}
FOR(i,1,n) FOR(j,1,n) if(f[i][j].size()) {
FOR(h,1,n) FOR(u,1,n) FOR(v,1,n) if(g[h][u][h][v]) {
o[i][j][h][u][v]=!on_segment(f[h][u][0],f[h][v][0],f[i][j][0]);
}
}
vis[1]=1;
w[1]=1;
dfs(1);
cout << res/2 << '\n';
return 0;
}
/*
6
0 0 1 0
0 -1 1 -1
0 0 3 3
1 0 3 2
6 0 3 3
5 0 3 2
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2089ms
memory: 7940kb
input:
12 1754 -1894 1131 163 -1361 350 1392 -1473 1672 -1863 -634 1706 -1869 498 -432 700 355 1737 -1052 -771 590 1273 -158 778 -1599 1914 -1543 -1839 191 995 -1589 -1387 -1126 -30 854 -1504 -1127 -794 -234 523 -653 -1719 903 -1828 -325 -1165 1958 -1015
output:
154903
result:
ok single line: '154903'
Test #2:
score: 0
Accepted
time: 2018ms
memory: 8700kb
input:
12 -269 1562 1704 -519 863 -434 1536 1614 -1620 -1015 -153 56 -429 -806 -671 -720 -1234 1163 1228 58 1067 247 -243 181 1561 1598 494 1380 -1416 -376 -755 -1550 87 -1902 -44 -294 -759 646 -780 -1396 -765 -1066 -1124 277 -1751 -1406 -737 1614
output:
110265
result:
ok single line: '110265'
Test #3:
score: 0
Accepted
time: 2154ms
memory: 7972kb
input:
12 1056 76 -284 1291 371 935 392 -503 1968 -1654 46 -548 -1890 1887 984 1067 -491 3 1659 246 413 211 32 -110 -693 -147 406 -1104 -496 -435 -35 -84 -1542 -1183 1331 1722 -327 -1994 -1525 821 915 1175 1177 -1263 -547 -1872 -1606 -1574
output:
136696
result:
ok single line: '136696'
Test #4:
score: 0
Accepted
time: 37ms
memory: 7912kb
input:
7 133 -774 -212 650 664 -137 -132 50 -283 -436 -211 335 -412 37 827 -279 -184 -229 -788 -950 -573 139 -971 488 -357 307 -258 14
output:
73
result:
ok single line: '73'
Test #5:
score: 0
Accepted
time: 260ms
memory: 6792kb
input:
10 981 1743 1818 833 1818 833 1961 -394 1961 -394 1354 -1472 1354 -1472 231 -1987 231 -1987 -981 -1743 -981 -1743 -1818 -833 -1818 -833 -1961 394 -1961 394 -1354 1472 -1354 1472 -231 1987 -231 1987 981 1743
output:
3138
result:
ok single line: '3138'
Test #6:
score: 0
Accepted
time: 814ms
memory: 7616kb
input:
11 363 1967 1369 1458 1369 1458 1940 487 1940 487 1895 -639 1895 -639 1249 -1562 1249 -1562 206 -1989 206 -1989 -902 -1785 -902 -1785 -1724 -1014 -1724 -1014 -1998 79 -1998 79 -1638 1147 -1638 1147 -758 1851 -758 1851 363 1967
output:
27490
result:
ok single line: '27490'
Test #7:
score: 0
Accepted
time: 951ms
memory: 8148kb
input:
12 1201 1599 1840 784 1840 784 1985 -241 1985 -241 1599 -1201 1599 -1201 784 -1840 784 -1840 -241 -1985 -241 -1985 -1201 -1599 -1201 -1599 -1840 -784 -1840 -784 -1985 241 -1985 241 -1599 1201 -1599 1201 -784 1840 -784 1840 241 1985 241 1985 1201 1599
output:
71780
result:
ok single line: '71780'
Test #8:
score: 0
Accepted
time: 207ms
memory: 6432kb
input:
9 6 2000 1290 1528 1290 1528 1971 341 1971 341 1729 -1005 1729 -1005 678 -1882 678 -1882 -690 -1877 -690 -1877 -1735 -995 -1735 -995 -1969 353 -1969 353 -1281 1536 -1281 1536 6 2000
output:
1360
result:
ok single line: '1360'
Test #9:
score: 0
Accepted
time: 0ms
memory: 8064kb
input:
6 201 980 980 -201 201 980 -201 -980 201 980 -980 201 980 -201 -201 -980 980 -201 -980 201 -201 -980 -980 201
output:
0
result:
ok single line: '0'
Test #10:
score: 0
Accepted
time: 254ms
memory: 6768kb
input:
10 803 596 815 -580 803 596 -300 -954 803 596 -1000 -10 803 596 -319 948 815 -580 -300 -954 815 -580 -1000 -10 815 -580 -319 948 -300 -954 -1000 -10 -300 -954 -319 948 -1000 -10 -319 948
output:
33
result:
ok single line: '33'
Test #11:
score: 0
Accepted
time: 1ms
memory: 5732kb
input:
4 0 0 0 1 0 1 1 1 1 1 1 0 1 0 0 0
output:
1
result:
ok single line: '1'
Test #12:
score: 0
Accepted
time: 6ms
memory: 8112kb
input:
10 0 0 0 1 1 0 1 1 2 0 2 1 0 0 1 0 0 1 1 1 0 2 1 2 0 3 1 3 0 4 1 4 0 5 1 5 0 6 1 6
output:
0
result:
ok single line: '0'
Test #13:
score: 0
Accepted
time: 8ms
memory: 7848kb
input:
10 0 0 0 1 1 0 1 1 2 0 2 1 3 0 3 1 0 0 1 0 0 1 1 1 0 2 1 2 0 3 1 3 0 4 1 4 0 5 1 5
output:
0
result:
ok single line: '0'
Test #14:
score: 0
Accepted
time: 8ms
memory: 6028kb
input:
10 0 0 0 1 1 0 1 1 2 0 2 1 3 0 3 1 4 0 4 1 0 0 1 0 0 1 1 1 0 2 1 2 0 3 1 3 0 4 1 4
output:
240
result:
ok single line: '240'
Test #15:
score: 0
Accepted
time: 1ms
memory: 5948kb
input:
3 416 909 580 -815 580 -815 -996 -95 -996 -95 416 909
output:
1
result:
ok single line: '1'
Test #16:
score: 0
Accepted
time: 1ms
memory: 5664kb
input:
4 287 958 958 -287 958 -287 -287 -958 -287 -958 -958 287 -958 287 287 958
output:
1
result:
ok single line: '1'
Test #17:
score: 0
Accepted
time: 4ms
memory: 5700kb
input:
5 271 963 999 40 999 40 347 -938 347 -938 -785 -620 -785 -620 -832 555 -832 555 271 963
output:
6
result:
ok single line: '6'
Test #18:
score: 0
Accepted
time: 4ms
memory: 5896kb
input:
6 210 978 952 307 952 307 741 -671 741 -671 -210 -978 -210 -978 -952 -307 -952 -307 -741 671 -741 671 210 978
output:
10
result:
ok single line: '10'
Test #19:
score: 0
Accepted
time: 34ms
memory: 8100kb
input:
7 784 621 974 -226 974 -226 431 -902 431 -902 -437 -900 -437 -900 -976 -219 -976 -219 -780 626 -780 626 3 1000 3 1000 784 621
output:
85
result:
ok single line: '85'
Test #20:
score: 0
Accepted
time: 35ms
memory: 7856kb
input:
8 765 644 996 -85 996 -85 644 -765 644 -765 -85 -996 -85 -996 -765 -644 -765 -644 -996 85 -996 85 -644 765 -644 765 85 996 85 996 765 644
output:
167
result:
ok single line: '167'
Test #21:
score: 0
Accepted
time: 189ms
memory: 6352kb
input:
9 511 860 944 330 944 330 935 -354 935 -354 489 -872 489 -872 -186 -983 -186 -983 -774 -633 -774 -633 -1000 13 -1000 13 -758 652 -758 652 -161 987 -161 987 511 860
output:
1360
result:
ok single line: '1360'
Test #22:
score: 0
Accepted
time: 227ms
memory: 7892kb
input:
10 583 813 949 315 949 315 953 -303 953 -303 593 -805 593 -805 6 -1000 6 -1000 -583 -813 -583 -813 -949 -315 -949 -315 -953 303 -953 303 -593 805 -593 805 -6 1000 -6 1000 583 813
output:
3138
result:
ok single line: '3138'
Test #23:
score: 0
Accepted
time: 0ms
memory: 5916kb
input:
6 275 961 961 -275 275 961 -275 -961 275 961 -961 275 961 -275 -275 -961 961 -275 -961 275 -275 -961 -961 275
output:
0
result:
ok single line: '0'
Test #24:
score: 0
Accepted
time: 275ms
memory: 6744kb
input:
10 538 843 968 -251 538 843 60 -998 538 843 -931 -366 538 843 -636 772 968 -251 60 -998 968 -251 -931 -366 968 -251 -636 772 60 -998 -931 -366 60 -998 -636 772 -931 -366 -636 772
output:
33
result:
ok single line: '33'
Test #25:
score: 0
Accepted
time: 1ms
memory: 5940kb
input:
3 -1038 -1453 1531 1687 1513 -565 -1222 86 -1459 652 1424 -1051
output:
1
result:
ok single line: '1'
Test #26:
score: 0
Accepted
time: 199ms
memory: 6704kb
input:
9 692 699 21 -24 -888 -857 679 613 -502 848 877 -645 645 -877 -848 502 24 -21 -699 -692 -613 -679 857 888 613 -679 -857 888 -645 -877 848 502 -24 -21 699 -692
output:
1341
result:
ok single line: '1341'
Test #27:
score: 0
Accepted
time: 1657ms
memory: 8440kb
input:
12 765 -1332 -1660 1621 -1835 -1787 1842 1004 1817 1372 -1463 -1815 -1621 -1660 1332 765 1787 -1835 -1004 1842 -1372 1817 1815 -1463 1621 1660 -1332 -765 -1787 1835 1004 -1842 1372 -1817 -1815 1463 -1621 1660 1332 -765 -1004 -1842 1787 1835 1815 1463 -1372 -1817
output:
71458
result:
ok single line: '71458'
Test #28:
score: 0
Accepted
time: 1705ms
memory: 8512kb
input:
12 1966 -1991 -1683 872 -1751 -1825 1764 1837 -1478 -1856 1129 1527 1991 1966 -872 -1683 1825 -1751 -1837 1764 -1527 1129 1856 -1478 1683 872 -1966 -1991 -1764 1837 1751 -1825 -1129 1527 1478 -1856 1683 -872 -1966 1991 1751 1825 -1764 -1837 -1129 -1527 1478 1856
output:
84355
result:
ok single line: '84355'
Test #29:
score: 0
Accepted
time: 450ms
memory: 8000kb
input:
11 -1999 2000 2000 -2000 2000 2000 -2000 -1999 1999 1999 -1999 -1998 -1999 -1999 1998 1999 -1998 1998 1998 -1997 1999 -1998 -1999 1999 1998 1997 -1998 -1998 1997 -1997 -1996 1997 1998 -1998 -1997 1998 1997 1996 -1997 -1997 1996 -1996 -1995 1996
output:
11796
result:
ok single line: '11796'
Test #30:
score: 0
Accepted
time: 1ms
memory: 5732kb
input:
3 231 -1456 -1490 145 -841 -1120 1518 1270 1437 1223 -900 -1187
output:
1
result:
ok single line: '1'
Test #31:
score: 0
Accepted
time: 2ms
memory: 3848kb
input:
10 -453 -43 844 -58 416 566 -25 -667 -444 -392 835 291 987 438 -596 -539 407 -221 -16 120 -274 -563 665 462 -248 -428 639 327 163 874 228 -975 -559 432 950 -533 919 150 -528 -251
output:
0
result:
ok single line: '0'
Test #32:
score: 0
Accepted
time: 331ms
memory: 6900kb
input:
10 5 131 75 705 762 721 246 601 448 664 695 977 539 605 792 194 790 723 959 720 760 826 557 777 702 166 857 333 396 530 659 122 631 947 631 667 307 621 706 952
output:
5594
result:
ok single line: '5594'
Test #33:
score: 0
Accepted
time: 392ms
memory: 6852kb
input:
10 566 809 32 814 21 150 142 792 251 793 552 248 894 79 593 417 726 932 560 15 611 588 5 252 581 654 705 346 740 665 964 863 824 113 453 466 513 168 60 354
output:
4773
result:
ok single line: '4773'
Test #34:
score: 0
Accepted
time: 390ms
memory: 7900kb
input:
10 281 474 758 182 368 106 61 646 798 844 960 555 845 584 969 196 49 850 250 884 234 775 393 933 133 361 897 392 942 309 655 984 249 503 269 966 77 533 279 314
output:
5402
result:
ok single line: '5402'
Test #35:
score: 0
Accepted
time: 382ms
memory: 7932kb
input:
10 711 385 738 683 142 213 222 997 510 922 644 592 938 919 135 53 490 916 973 670 991 156 923 526 11 66 165 573 473 283 232 769 474 742 910 606 140 835 314 63
output:
4469
result:
ok single line: '4469'
Test #36:
score: 0
Accepted
time: 2145ms
memory: 8152kb
input:
12 -1965 -1738 1228 1772 861 -1399 -694 1195 -1639 1604 1657 -1329 -1772 -1228 1738 1965 1399 -861 -1195 694 1329 -1657 -1604 1639 1965 -1738 -1228 1772 694 1195 -861 -1399 1639 1604 -1657 -1329 1772 -1228 -1738 1965 -1399 -861 1195 694 -1329 -1657 1604 1639
output:
108424
result:
ok single line: '108424'
Test #37:
score: 0
Accepted
time: 0ms
memory: 7648kb
input:
3 0 0 0 1 0 1 1 0 1 0 0 0
output:
1
result:
ok single line: '1'