QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#190466 | #1945. Finding Polly | SolitaryDream# | WA | 474ms | 7740kb | C++20 | 3.0kb | 2023-09-28 22:19:23 | 2023-09-28 22:19:24 |
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 double db;
const db eps=1e-6;
int sgn(db x) {
return x<-eps?-1:x>eps;
}
struct Point {
db 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 db &s) const{
return {x*s,y*s};
}
db Len2() const {
return x*x+y*y;
}
bool zero() const {
return !sgn(x)&&!sgn(y);
}
};
db 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(!sgn(det(a-b,c-d))) 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==2 && w[2]==2) 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-2) 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)
{
cin >> a[i].x >> a[i].y >> b[i].x >> b[i].y;
// 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);
cout << res/2 << '\n';
vis[1]=0;
// res = 0;
// vis[2]=1;
// w[1]=2;
// dfs(1);
// vis[2]=0;
// 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: 398ms
memory: 7660kb
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: 386ms
memory: 7612kb
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: 474ms
memory: 7700kb
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: 2ms
memory: 6132kb
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: 0ms
memory: 6460kb
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: 68ms
memory: 7084kb
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: 187ms
memory: 7448kb
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: 3ms
memory: 6468kb
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: 7740kb
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: -100
Wrong Answer
time: 11ms
memory: 6500kb
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:
977
result:
wrong answer 1st lines differ - expected: '33', found: '977'