C++14(g++5.4) 解法, 执行用时: 10ms, 内存消耗: 384K, 提交时间: 2020-10-19 20:48:21

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#define INF 2000000000
using namespace std;
typedef long long ll;
int n,vis[255],match[255]={0},seg[255][4];
int X[255],Y[255],cx=0,cy=0;
bool mat[255][255]={0};
int read(){
	int f=1,x=0;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
	while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
	return f*x; 
}	
int Edmond(int S){
	for(int i=1;i<=cy;i++){
		if(mat[S][i]&&!vis[i]){
			vis[i]=1;
			if(!match[i]||Edmond(match[i])){
				match[i]=S;
				return 1;
			}
		}
	}
	return 0;
}
void init(){
	n=read();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=4;j++)
			seg[i][j]=read();
		if(seg[i][1]==seg[i][3]){
			Y[++cy]=i;//竖直 
			if(seg[i][2]>seg[i][4])
				swap(seg[i][2],seg[i][4]);
		}else {
			X[++cx]=i;//水平
			if(seg[i][1]>seg[i][3])
				swap(seg[i][1],seg[i][3]);
		} 
	}
	for(int i=1;i<=cx;i++)
		for(int j=1;j<=cy;j++)
			if(seg[Y[j]][1]>=seg[X[i]][1]&&seg[Y[j]][1]<=seg[X[i]][3]&&
                seg[X[i]][2]>=seg[Y[j]][2]&&seg[X[i]][2]<=seg[Y[j]][4])
                mat[i][j]=1;
}
void solve(){
	int ans=0;
	for(int i=1;i<=cx;i++){
		memset(vis,0,sizeof(vis));
		if(Edmond(i))ans++;
	}
	printf("%d\n",n-ans);
}
int main(){
	init();
	solve();
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 6ms, 内存消耗: 532K, 提交时间: 2020-10-20 14:33:00

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=255,MAXM=MAXN*MAXN;
struct Po
{
	int sx,sy,tx,ty;
}a[MAXN];
struct Edge
{
	int to,next;
}edge[MAXM];
int head[MAXN],match[MAXN],n,ans,tot=1;
bool vis[MAXN];
void addedge(int u,int v)
{
	edge[tot]=(Edge){v,head[u]};
	head[u]=tot++;
}
bool dfs(int u)
{
	for(int i=head[u];i;i=edge[i].next)
	{
		int v=edge[i].to;
		if(!vis[v])
		{
			vis[v]=1;
			if(!match[v]||dfs(match[v]))
			{
				match[v]=u;
				return true;
			}
		}
	}
	return false;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	scanf("%d%d%d%d",&a[i].sx,&a[i].sy,&a[i].tx,&a[i].ty);
	for(int i=1;i<=n;i++)
	{
		if(a[i].sx>a[i].tx)
		swap(a[i].sx,a[i].tx);
		if(a[i].sy>a[i].ty)
		swap(a[i].sy,a[i].ty);
	}
	for(int i=1;i<=n;i++)
	if(a[i].sx==a[i].tx)
	{
		for(int j=1;j<=n;j++)
		if(a[j].sy==a[j].ty&&a[j].sx<=a[i].sx&&a[j].tx>=a[i].sx&&a[i].sy<=a[j].sy&&a[i].ty>=a[j].sy)
		addedge(i,j);
	}
	for(int i=1;i<=n;i++)
	{
		memset(vis,0,sizeof(vis));
		ans+=dfs(i);
	}
	printf("%d\n",n-ans);
	return 0;
}