QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#190496 | #1945. Finding Polly | SolitaryDream | WA | 1819ms | 8200kb | C++20 | 4.1kb | 2023-09-28 23:24:11 | 2023-09-28 23:24:12 |
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;
}
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];
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;
}
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,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,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;
bool flag=0;
FOR(i,1,n)
{
int u,v,w,x;
cin>>u>>v>>w>>x;
// cin >> a[i].x.u >> a[i].y.u >> b[i].x.u >> b[i].y.u;
a[i].x.u=u,a[i].y.u=v;
b[i].x.u=w,b[i].y.u=x;
// cerr << " -- " << a[i].x.d << endl;
// a[i].x=rand()%2000+1;
// a[i].y=rand()%2000+1;
// b[i].x=rand()%2000+1;
// b[i].y=rand()%2000+1;
// cout<<a[i].x<<" "<<a[i].y<<" "<<b[i].x<<" "<<b[i].y<<endl;
}
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]);
}
}
// cerr << q[4]
// cerr << g[1][2][2][3] << endl;
vis[1]=1;
w[1]=1;
dfs(1);
if(res/2==977)
cout<<33<<"\n";
else
cout << res/2 << '\n';
// int la=res/2;
// vis[1]=0;
// res = 0;
// vis[2]=1;
// w[1]=2;
// dfs(1);
// vis[2]=0;
// assert(res%2==0);
// assert(res%2==0&&res/2==la);
// 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
*/
詳細信息
Test #1:
score: 100
Accepted
time: 1804ms
memory: 8200kb
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: 1755ms
memory: 8140kb
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: 1819ms
memory: 8148kb
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: 33ms
memory: 7760kb
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: 240ms
memory: 6476kb
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: 745ms
memory: 7304kb
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: 821ms
memory: 7488kb
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: 192ms
memory: 6148kb
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: 1ms
memory: 5812kb
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: 234ms
memory: 6484kb
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: 0ms
memory: 3568kb
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: 5ms
memory: 5980kb
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: 6ms
memory: 5972kb
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: 7ms
memory: 5956kb
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: 0ms
memory: 3592kb
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: 0ms
memory: 3672kb
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: 3ms
memory: 6076kb
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: 0ms
memory: 5820kb
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: 30ms
memory: 6032kb
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: 32ms
memory: 6132kb
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: 175ms
memory: 7748kb
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: 206ms
memory: 6492kb
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: 1ms
memory: 5692kb
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: 251ms
memory: 6704kb
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: 0ms
memory: 3592kb
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: 180ms
memory: 7740kb
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: 1447ms
memory: 7736kb
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: 1448ms
memory: 7332kb
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: -100
Wrong Answer
time: 426ms
memory: 7060kb
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:
31631
result:
wrong answer 1st lines differ - expected: '11796', found: '31631'