题意：平面内有N头牛$Nle 10$john从（0,0）出发，最后回到(0,0)
只有走到牛那里john才可以改变方向，否则沿着直线走
问john经过每一头牛并且在每一头牛出恰好改变方向一次的方案（牛可以经过多次，但只能改变方向一次）
（dfs没写出来）
看到$nle 10$就容易多了
用next_permutation枚举改变方向的牛的顺序
判断是否成立即可
#include<cstdio> #include<iostream> #include<cstring> #include<cctype> #include<algorithm> using namespace std; #define olinr return #define _ 0 #define love_nmr 0 #define DB double inline int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) { if(ch=='-') f=-f; ch=getchar(); } while(isdigit(ch)) { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } inline void put(int x) { if(x<0) { x=-x; putchar('-'); } if(x>9) put(x/10); putchar(x%10+'0'); } int n; int ans; int a[15]; struct node { int x; int y; }cow[15]; bool pd[15]; inline bool doit() { int lx=0; //上头牛 int ly=0; for(int i=0;i<n;i++) { int x=cow[a[i]].x; //当前牛 int y=cow[a[i]].y; int nx=cow[a[i+1]].x; //下头牛 int ny=cow[a[i+1]].y; if(x!=lx&&y!=ly) return false; //无法到达 if(x!=nx&&y!=ny) return false; int xx=x-lx; int yy=y-ly; int xxx=nx-x; int yyy=ny-y; if(xx*xxx+yy*yyy>0) return false; //没拐弯（向量点乘判断） lx=x; ly=y; } return true; } int main() { n=read(); for(int i=0;i<=n;i++) a[i]=i; for(int i=0;i<n;i++) { cow[i].x=read(); cow[i].y=read(); } do { ans+=doit(); }while(next_permutation(a,a+n)); put(ans); olinr ~~(0^_^0)+love_nmr; }
感谢rqj dalao对蒟蒻的指点