【Codeforces 698D】Limak and Shooting Points



#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;}

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(){
	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;}
	return 0;