Arc076_E Connected?

题目大意

给定$H\times W$的网格$(W,H\leq 10^8)$上的$N$对顶点，即两线交叉的交叉点而非格子内部$(N\leq 10^5)$，求是否存在至少一种方案使得每对点之间都有一条不出网格边界的曲线且曲线互不相交。

题解

假设当前连线情况确定，两点之间是否存在意在连线的可能仅与两点间的连通性由有关，很显然当一对点有任意一点不在边界上，那么由于所有点两两不同，那么连接这对点对其他点对的连通性毫无影响，所以我们只需要判断所有点都在边界上的那些点对之间有没有两两交叉的即可。

可以将方格边界上顺时针标号，将每个对点看做一个区间，判断区间之间是否只存在包含关系即可，这个用类似括号序列一样的方法用栈维护递增的左端点，最后只需要判断栈中有没有未删掉的元素。

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#define LL long long

#define M 400020

using namespace std;

int read(){

	int nm=0,fh=1; int cw=getchar();

	for(;!isdigit(cw);cw=getchar()) if(cw=='-') fh=-fh;

	for(;isdigit(cw);cw=getchar()) nm=nm*10+(cw-'0');

	return nm*fh;

}

struct num{

	int pos,id;num(){pos=0,id=0;}

	num(int _pos,int _id){pos=_pos,id=_id;}

}p[M],S[M];

int vis[M],H,W,n,top;

bool on(int x,int y){return x==0||y==0||x==H||y==W;}

int bas(int x,int y){

	if(!x) return y; if(y==W) return W+x;

	if(x==H) return W+H+W-y; return W+H+W+H-x;

}

bool cmp(num x,num y){return x.pos<y.pos;}

int main(){

	H=read(),W=read(),n=read();

	for(int i=1;i<=n;i++){

		int x=read(),y=read(),xx=read(),yy=read();

		if(!on(x,y)||!on(xx,yy)){i--,n--;continue;}

		int L=bas(x,y),R=bas(xx,yy); if(L>R) swap(L,R);

		p[(i<<1)-1]=num(L,i),p[i<<1]=num(R,i);

	} n<<=1,sort(p+1,p+n+1,cmp);

	for(int i=1;i<=n;i++){if(S[top].id!=p[i].id||!top) top++,S[top]=p[i];else top--;}

	puts(top?"NO":"YES"); return 0;

}

巴特西

Arc076_E Connected?

最新文章

热门文章