题解
把线段抽象成点，线段相交就连一条边，然后求一个最大独立集。
由于在二分图中，最大匹配就等于最小顶点覆盖，并且对于图来说，最大独立集加上最小顶点覆盖就等于点个数，所以直接上二分图匹配就行了。
线段求交…计算几何1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
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;
}