本人两次提交都 CE 了。本机测试完全没问题,在洛谷 IDE 上都时候没问题有时候 RE 有时候 CE ,真不知道出什么幺蛾子了。 QAQ
代码:
#include<bits/stdc++.h>
using namespace std;
const int N=260;
int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+ch-'0';
ch=getchar();
}
return x*f;
}
int n,totx,toty,cnt,head[N],vis[N],match[N],ans;
struct segment{
int xl,yl,xr,yr;
}X[N],Y[N],a;
struct edge{
int to,nxt;
}e[N*N];
void add(int u,int v){
e[++cnt].to=v,e[cnt].nxt=head[u],head[u]=cnt;
}
bool check(segment a,segment b){
return b.xl<=a.xl&&a.xl<=b.xr&&a.yl<=b.yl&&b.yl<=a.yr;
}
int dfs(int u){
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(vis[v])continue;
vis[v]=1;
if(!match[v]||dfs(match[v])){
match[v]=u;
return 1;
}
}
return 0;
}
int main(){
n=read();
for(int i=1;i<=n;i++){
a.xl=read(),a.yl=read(),a.xr=read(),a.yr=read();
if(a.xl>a.xr)swap(a.xl,a.xr);
if(a.yl>a.yr)swap(a.yl,a.yr);
if(a.xl==a.xr)X[++totx]=a;
if(a.yl==a.yr)Y[++toty]=a;
}
for(int i=1;i<=totx;i++)for(int j=1;j<=toty;j++)if(check(X[i],Y[j]))add(i,j);
for(int i=1;i<=totx;i++){
memset(vis,0,sizeof(vis));
ans+=dfs(i);
}
printf("%d",n-ans);
return 0;
}