2517961_ac_0ms_192k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <math.h>
#include <string.h>

int pot[251][2];
int n, m;
int map[130][130];
int visited[130];
int left, right;
int line[200][2], l;

int max(int a,int b)
{
	return a>b?a:b;
}

int min(int a,int b)
{
	return a<b?a:b;
}

void dfs(int v)
{
	int i;

	visited[v] = 1;
	if(pot[v*2][0]==0)
		left = 1;
	if(pot[v*2][0]==n)
		right = 1;
	for(i = 0; i < (m+1)/2; i++)
	{
		if(map[v][i]&&!visited[i])
			dfs(i);
	}
}

int dis(int i,int j)
{
	if(abs(pot[i][0]-pot[j][0])==1&&abs(pot[i][1]-pot[j][1])==2)
		return 1;
	if(abs(pot[i][0]-pot[j][0])==2&&abs(pot[i][1]-pot[j][1])==1)
		return 1;
	return 0;
}

int multi(int a,int b,int c)
{
	return (pot[a][0]-pot[c][0])*(pot[b][1]-pot[c][1])-(pot[b][0]-pot[c][0])*(pot[a][1]-pot[c][1]);
}

int cross(int a,int b,int c,int d)
{
	if(max(pot[a][0],pot[b][0])>min(pot[c][0],pot[d][0])&&max(pot[c][0],pot[d][0])>min(pot[a][0],pot[b][0]))
	{
		if(max(pot[a][1],pot[b][1])>min(pot[c][1],pot[d][1])&&max(pot[c][1],pot[d][1])>min(pot[a][1],pot[b][1]))
		{
			if((multi(c,b,a)*multi(b,d,a)>0)&&(multi(a,d,c)*multi(d,b,c)>0))
				return 1;
		}
	}
	return 0;
}

int no_ins(int i, int j)
{
	int k;
	int a, b;

	for(k = 0; k < l; k++)
	{
		a = line[k][0];b = line[k][1];
		if(cross(a,b,i,j))
			return 0;
	}
	return 1;
}

int main()
{
	int i, j;

	while(scanf("%d%d",&n,&m)==2&&n&&m)
	{
		l = 0;
		memset(visited,0,sizeof(visited));
		memset(map,0,sizeof(map));
		for(i = 0; i < m; i++)
			scanf("%d%d",&pot[i][0],&pot[i][1]);
		for(i = 2; i < m; i++)
		{
			for(j = i-2; j >= 0; j-=2)
			{
				if(dis(i,j)&&no_ins(i,j))
				{
					if(i%2==0)
						map[i/2][j/2] = map[j/2][i/2] = 1;
					line[l][0] = i,line[l][1] = j;
					l++;
				}
			}
		}
		
		for(i = 0; i < (m+1)/2; i++)
		{
			if(!visited[i])
			{
				left = right = 0;
				dfs(i);
				if(left&&right)
				{
					printf("yes\n");
					goto con;
				}
			}
		}
		printf("no\n");
con:
		;
	}
	return 1;
}