QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#190454 | #1945. Finding Polly | SolitaryDream# | WA | 361ms | 8232kb | C++20 | 2.3kb | 2023-09-28 21:40:49 | 2023-09-28 21:40:50 |
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 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;
}
};
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 ;
++res;
return ;
}
++p;
FOR(i,2,n) if(!vis[i]) {
vis[i]=1;
w[p]=i;
dfs(p);
vis[i]=0;
}
}
int main() {
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;
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]=sgn((f[i][j][0]-f[k][h][0]).Len2());
}
}
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 << g[1][2][2][3] << endl;
vis[1]=1;
w[1]=1;
dfs(1);
cout << res/2 << '\n';
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 361ms
memory: 8232kb
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:
167763
result:
wrong answer 1st lines differ - expected: '154903', found: '167763'