QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#190470#1945. Finding PollySolitaryDream#WA 392ms7592kbC++203.1kb2023-09-28 22:26:332023-09-28 22:26:34

Judging History

This is the latest submission verdict.

  • [2023-09-28 22:26:34]
  • Judged
  • Verdict: WA
  • Time: 392ms
  • Memory: 7592kb
  • [2023-09-28 22:26:33]
  • 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-12;
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;
    // 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: 0
Wrong Answer
time: 392ms
memory: 7592kb

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:

147024

result:

wrong answer 1st lines differ - expected: '154903', found: '147024'