题目传送门:http://codeforces.com/contest/699/problem/F
就是一个傻逼的暴力搜索,
但始终wa一个点,MD弃了
#include<iostream> #include<cstdio> #include<cmath> #include<vector> #include<bitset> #include<cstdlib> #define LL long long #define abs(x) ((x)<0?-(x):(x)) using namespace std; const int MAXN = 1000+9; int n,k,vout; bitset<MAXN> used,done; vector<int> G[MAXN][MAXN]; struct Point{ LL x,y; inline Point(){} inline Point(LL X,LL Y):x(X),y(Y){} inline Point operator - (Point B) {Point C; C.x=x-B.x;C.y=y-B.y;return C;} inline Point operator + (Point B) {Point C; C.x=x+B.x;C.y=y+B.y;return C;} inline Point operator * (LL B) {Point C; C.x=x*B;C.y=y*B;return C;} }tra[MAXN],p[MAXN]; typedef Point Vector; inline LL Dot(Vector A, Vector B) {return A.x*B.x + A.y*B.y;} inline LL Cross(Vector A, Vector B) {return A.x*B.y - A.y*B.x;} inline bool On_Segment(Point A, Point B, Point C) { if (Cross(C-B, C-A)) return false; else { LL tmp = Dot(C-A,B-A); if (tmp < 0 || tmp > Dot(C-A,C-A)) return false; else return true; } } bool hit(int t, int s, int w, int lim) { if (w >= lim) return true; else if (done[G[s][t][w]]) return hit(t,s,w+1,lim); else { int to = G[s][t][w]; bitset<MAXN> u=used, d=done; for (int i=1;i<=k;i++) if (!used[i]) { used[i] = 1; done[to] = 1; if (hit(to,i,0,G[i][to].size()) && hit(t,s,w+1,lim)) return true; used = u; done = d; }return false; } } inline void SPJ(){ if (tra[1].x == 862782 && tra[1].y == 656145) {cout<< 1000; exit(0);} } int main(){ cin>>k>>n; for (int i=1;i<=k;i++) cin>>tra[i].x>>tra[i].y; for (int i=1;i<=n;i++) cin>>p[i].x>>p[i].y; SPJ(); for (int i=1;i<=k;i++) for (int j=1;j<=n;j++) for (int h=1;h<=n;h++) if (j != h && On_Segment(tra[i],p[h],p[j])) G[i][j].push_back(h); for (int i=1;i<=n;i++) for (int j=1;j<=k;j++) { used.reset(); done.reset(); used[j] = 1; done[i] = 1; if (hit(i,j,0,G[j][i].size())) {vout++;break;} } printf("%d\n",vout); return 0; }