【NOIP2012模拟8.6】三条线

这题暴力离散化+dfs即可。详见标。
上标：

#include<cstdio>
#include<algorithm>
#define N 50010
using namespace std;
struct node{int x,y,fr;}a[N],b[N];
int n,X[N],Y[N],to1[N],to2[N],cnt=0,tot=0;
bool bz1[N],bz2[N],check=0;

inline int read()
{
	int x=0; char c=getchar();
	while (c<'0' || c>'9') c=getchar();
	while (c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x;
}

int cmp(node x,node y) {return x.x==y.x ? x.y<y.y : x.x<y.x;}

int cmp1(node x,node y) {return x.y==y.y ? x.x<y.x : x.y<y.y;}

void dfs(int x,int s)
{
	if (check) return;
	if (x>n) {check=1; return;}
	if (bz1[to1[x]] || bz2[to2[x]]) {dfs(x+1,s); return;}
	if (s==3) return;
	bz1[to1[x]]=1;
	dfs(x+1,s+1);
	bz1[to1[x]]=0;
	
	bz2[to2[x]]=1;
	dfs(x+1,s+1);
	bz2[to2[x]]=0;
}

int main()
{
	freopen("line.in","r",stdin);
	freopen("line.out","w",stdout);
	n=read();
	for (int i=1;i<=n;i++)
	{
		X[i]=read(),Y[i]=read();
		a[i]=b[i]=(node){X[i],Y[i],i};
	}
	sort(a+1,a+n+1,cmp);
	sort(b+1,b+n+1,cmp1);
	for (int i=1;i<=n;i++)
	{
		to1[a[i].fr]=++cnt;
		while (a[i].x==a[i+1].x) to1[a[++i].fr]=cnt;
	}
	for (int i=1;i<=n;i++)
	{
		to2[b[i].fr]=++tot;
		while (b[i].y==b[i+1].y) to2[b[++i].fr]=tot;
	}
	dfs(1,0);
	if (check) puts("1");
	else puts("0");
	return 0;
}