QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#190471#1945. Finding PollySolitaryDream#WA 463ms8052kbC++203.1kb2023-09-28 22:31:162023-09-28 22:31:17

Judging History

This is the latest submission verdict.

  • [2023-09-28 22:31:17]
  • Judged
  • Verdict: WA
  • Time: 463ms
  • Memory: 8052kb
  • [2023-09-28 22:31:16]
  • Submitted

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-8;
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,3,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;
    // 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: 388ms
memory: 7700kb

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: 384ms
memory: 7580kb

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: 463ms
memory: 7948kb

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

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

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: 67ms
memory: 7200kb

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: 182ms
memory: 8052kb

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

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

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

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:

750

result:

wrong answer 1st lines differ - expected: '33', found: '750'