利用二分图匹配求最大独立集
本题的边一定平行于坐标轴，且同向的线段一定不重合，这是经典的二分图建图方法，本题要求的是最大不重合的线段数，那就是求二分图的最大独立集，最大独立集=总点数-最大匹配数。
本题有一个坑点，就是输入的数据不一定有序，也就是x1不一定比x2小
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int init(){
int rv=0,fh=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') fh=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
rv=(rv<<1)+(rv<<3)+c-'0';
c=getchar();
}
return rv*fh;
}
int n,x,y,g[300][300],match[300];
bool f[300];
struct line{
int a,b,c;
}col[300],row[300];
bool hungarian(int u){
for(int i=1;i<=g[u][0];i++){
int v=g[u][i];
if(!f[v]){
f[v]=1;
if(!match[v]||hungarian(match[v])){
match[v]=u;
return 1;
}
}
}
return 0;
}
int main(){
n=init();
for(int i=1;i<=n;i++){
int a=init(),b=init(),c=init(),d=init();
if(a==c){
col[++x].a=a;
col[x].b=min(b,d);
col[x].c=max(b,d);
}else{
row[++y].a=b;
row[y].b=min(a,c);
row[y].c=max(a,c);
}
}
for(int i=1;i<=x;i++){
for(int j=1;j<=y;j++){
if(col[i].b<=row[j].a&&col[i].c>=row[j].a&&row[j].b<=col[i].a&&row[j].c>=col[i].a){
g[i][++g[i][0]]=j;
}
}
}
int ans=0;
for(int i=1;i<=x;i++){
memset(f,0,sizeof(f));
if(hungarian(i)) ans++;
}
cout<<n-ans<<endl;
return 0;
}