QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#190486 | #1945. Finding Polly | SolitaryDream | RE | 0ms | 0kb | C++20 | 3.8kb | 2023-09-28 23:04:39 | 2023-09-28 23:04:39 |
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 {
ll u,d;
frac(ll u_=0,ll d_=1) {
u=u_,d=d_;
if(d<0) u=-u,d=-d;
ll g=__gcd(abs(u),d);
u/=g,d/=g;
}
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{
return frac(u*s.d+s.u*d,d*s.d);
}
frac operator -(const frac &s) const{
return frac(u*s.d-s.u*d,d*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-3) 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.u >> a[i].y.u >> b[i].x.u >> b[i].y.u;
// 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);
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: 0
Runtime Error
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