Problem Statement

 

On a two-dimensional plane, there are <var>N</var> red points and <var>N</var> blue points. The coordinates of the <var>i</var>-th red point are <var>(ai,bi)</var>, and the coordinates of the <var>i</var>-th blue point are <var>(ci,di)</var>.

A red point and a blue point can form a friendly pair when, the <var>x</var>-coordinate of the red point is smaller than that of the blue point, and the <var>y</var>-coordinate of the red point is also smaller than that of the blue point.

At most how many friendly pairs can you form? Note that a point cannot belong to multiple pairs.

Constraints

 

  • All input values are integers.
  • <var>1≤N≤100</var>
  • <var>0≤ai,bi,ci,di<2N</var>
  • <var>a1,a2,…,aN,c1,c2,…,cN</var> are all different.
  • <var>b1,b2,…,bN,d1,d2,…,dN</var> are all different.

Input

 

Input is given from Standard Input in the following format:

<var>N</var>
<var>a1</var> <var>b1</var>
<var>a2</var> <var>b2</var>
<var>:</var>
<var>aN</var> <var>bN</var>
<var>c1</var> <var>d1</var>
<var>c2</var> <var>d2</var>
<var>:</var>
<var>cN</var> <var>dN</var>

Output

 

Print the maximum number of friendly pairs.

Sample Input 1

 

3
2 0
3 1
1 3
4 2
0 4
5 5

Sample Output 1

 

2

For example, you can pair <var>(2,0)</var> and <var>(4,2)</var>, then <var>(3,1)</var> and <var>(5,5)</var>.

Sample Input 2

 

3
0 0
1 1
5 2
2 3
3 4
4 5

Sample Output 2

 

2

For example, you can pair <var>(0,0)</var> and <var>(2,3)</var>, then <var>(1,1)</var> and <var>(3,4)</var>.

Sample Input 3

 

2
2 2
3 3
0 0
1 1

Sample Output 3

 

0

It is possible that no pair can be formed.

Sample Input 4

 

5
0 0
7 3
2 2
4 8
1 6
8 5
6 9
5 4
9 1
3 7

Sample Output 4

 

5

Sample Input 5

 

5
0 0
1 1
5 5
6 6
7 7
2 2
3 3
4 4
8 8
9 9

Sample Output 5

 

4


题意：
给你n个红球，和n个蓝球。
以及每一个球的坐标。，现在定义 如果红球的x和y坐标都比蓝球小，那么红球可以和蓝球匹配。
一个球只能匹配一次。
问这n对球最大可以组成多少个有效pair

思路：
先根据坐标关系建立是否能匹配的关系，然后用二分图最大匹配算法的匈牙利算法跑即可。
不会的话可以去学习新算法。
细节见代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define ALL(x) (x).begin(), (x).end()
#define rt return
#define dll(x) scanf("%I64d",&x)
#define xll(x) printf("%I64d\n",x)
#define sz(a) int(a.size())
#define all(a) a.begin(), a.end()
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define gg(x) getInt(&x)
#define db(x) cout<<"== [ "<<x<<" ] =="<<endl;
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
ll powmod(ll a, ll b, ll MOD) {ll ans = 1; while (b) {if (b % 2)ans = ans * a % MOD; a = a * a % MOD; b /= 2;} return ans;}
inline void getInt(int* p);
const int maxn = 510;
const int inf = 0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
int n;
int a[maxn];
int b[maxn];
int c[maxn];
int d[maxn];
int can[maxn][maxn];
int vis[maxn];
int linker[maxn];
bool dfs(int x)
{
    repd(i, 1, n)
    {
        if (can[x][i] && vis[i] == 0)
        {
            vis[i] = 1;
            if (linker[i] == 0 || (dfs(linker[i])))// 没使用或者去寻找新的增广路
            {
                linker[i] = x;
                return 1;
            }
        }
    }
    return 0;
}
int main()
{
    //freopen("D:\\common_text\\code_stream\\in.txt","r",stdin);
    //freopen("D:\\common_text\\code_stream\\out.txt","w",stdout);
    gbtb;
    cin >> n;
    repd(i, 1, n)
    {
        cin >> a[i] >> b[i];
    }
    repd(i, 1, n)
    {
        cin >> c[i] >> d[i];
    }
    repd(i, 1, n)
    {
        repd(j, 1, n)
        {
            if (a[i] < c[j] && b[i] < d[j])
            {
                can[i][j] = 1;
            }
        }
    }
    int ans = 0;
    repd(i, 1, n)
    {
        memset(vis, 0, sizeof(vis));
        if (dfs(i))
        {
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

inline void getInt(int* p) {
    char ch;
    do {
        ch = getchar();
    } while (ch == ' ' || ch == '\n');
    if (ch == '-') {
        *p = -(getchar() - '0');
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 - ch + '0';
        }
    }
    else {
        *p = ch - '0';
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 + ch - '0';
        }
    }
}