P1556 幸福的路

題意：平面內有N頭牛$N\le 10$john從（0,0）出發，最后回到(0,0)

　　　只有走到牛那里john才可以改變方向，否則沿著直線走

　　　問john經過每一頭牛并且在每一頭牛出恰好改變方向一次的方案（牛可以經過多次，但只能改變方向一次）

?

?

（dfs沒寫出來）

看到$n\le 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對蒟蒻的指點