2190.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 2190 on 2006-04-03 at 01:02:14 */ 
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX = 128;
const int N_MAX = 512;
const int E_MAX = 65536;

vector<int> link[N_MAX];
bool vst[N_MAX];
int n, m, step[2*MAX][2];

class Edge {
public:
	int a, b;
	void make(int, int);
	bool intersect(int, int) const;
};
void Edge::make(int ca, int cb) {
	a = ca; b = cb;
}
bool Edge::intersect(int pa, int pb) const {
	int xa = step[a][0], ya = step[a][1], xb = step[b][0], yb = step[b][1];
	int x1 = step[pa][0], y1 = step[pa][1], x2 = step[pb][0], y2 = step[pb][1];
	if(min(xb, xa) > max(x2, x1)) return false;
	else if(min(x2, x1) > max(xb, xa)) return false;
	else if(min(yb, ya) > max(y2, y1)) return false;
	else if(min(y2, y1) > max(yb, ya)) return false;
	else {
		int c1 = (y1-yb)*(xa-xb)-(ya-yb)*(x1-xb);
		int c2 = (y2-yb)*(xa-xb)-(ya-yb)*(x2-xb);
		int c3 = (ya-y2)*(x1-x2)-(y1-y2)*(xa-x2);
		int c4 = (yb-y2)*(x1-x2)-(y1-y2)*(xb-x2);
		return c1 * c2 < 0 && c3 * c4 < 0;
	}
}

bool win(int, bool);
bool con(int, int);
inline int o(int, int);

int main()
{
	Edge edge[E_MAX];
	int i, j, k;

	while(scanf("%d %d", &n, &m) != EOF && m != 0) {
		int en = 0;
		for(i = 0; i <= n; i++)
			for(j = 0; j <= n; j++) link[o(i, j)].clear();
		for(i = 0; i < m; i++) {
			scanf("%d %d", &step[i][0], &step[i][1]);
			for(j = i&1; j < i; j += 2) {
				if(!con(i, j)) continue;
				bool can = true;
				for(k = 0; k < en && can; k++)
					if(edge[k].intersect(i, j)) can = false;
				if(can) {
					edge[en++].make(i, j);
					if(i & 1) continue;
					int o1 = o(step[i][0], step[i][1]), o2 = o(step[j][0], step[j][1]);
					link[o1].push_back(o2); link[o2].push_back(o1); 
				}
			}
		}
		bool through = false; memset(vst, false, sizeof(vst));
		for(i = 0; i <= n; i++)
			if(win(o(0, i), false) || win(o(i, 0), true)) through = true;
		printf("%s\n", through ? "yes" : "no");
	}
	
	return 0;
}

bool win(int b, bool up)
{
	if(!up && b/(n+1) == n) return true;
	else if(up && b%(n+1) == n) return true;
	else if(vst[b]) return false;
	vst[b] = true; int i;
	for(i = 0; i < (int)link[b].size(); i++)
		if(win(link[b][i], up)) return true;
	return false;
}
bool con(int o1, int o2)
{
	int sx = step[o1][0]-step[o2][0], sy = step[o1][1]-step[o2][1];
	if(sx == 0 || sy == 0) return false;
	else return (abs(sx)+abs(sy) == 3);
}
inline int o(int x, int y)
{
	return x * (n+1) + y;
}