|
|
#include <iostream>
|
|
|
#include <cstdio>
|
|
|
#include <cstring>
|
|
|
#include <vector>
|
|
|
#include <set>
|
|
|
#include <algorithm>
|
|
|
using namespace std;
|
|
|
|
|
|
typedef pair<int, int> PII;
|
|
|
#define x first
|
|
|
#define y second
|
|
|
|
|
|
const int N = 1010, M = N * N;
|
|
|
|
|
|
int e[M], h[N], idx, w[M], ne[M];
|
|
|
void add(int a, int b, int c = 0) {
|
|
|
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
|
|
|
}
|
|
|
|
|
|
int st[N], match[N];
|
|
|
int dfs(int u) {
|
|
|
for (int i = h[u]; ~i; i = ne[i]) {
|
|
|
int v = e[i];
|
|
|
if (st[v] == 1) continue;
|
|
|
st[v] = 1;
|
|
|
if (match[v] == -1 || dfs(match[v])) {
|
|
|
match[v] = u;
|
|
|
return 1;
|
|
|
}
|
|
|
}
|
|
|
return 0;
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
#ifndef ONLINE_JUDGE
|
|
|
freopen("POJ1548.in", "r", stdin);
|
|
|
#endif
|
|
|
int a, b;
|
|
|
while (true) {
|
|
|
memset(match, -1, sizeof match);
|
|
|
memset(st, 0, sizeof st);
|
|
|
|
|
|
memset(h, -1, sizeof h);
|
|
|
idx = 0;
|
|
|
|
|
|
vector<PII> vec;
|
|
|
while (true) {
|
|
|
cin >> a >> b;
|
|
|
if (a == 0 && b == 0) break;
|
|
|
if (a == -1 && b == -1) exit(0);
|
|
|
vec.push_back(make_pair(a, b));
|
|
|
}
|
|
|
|
|
|
sort(vec.begin(), vec.end());
|
|
|
|
|
|
vector<int> alls; // 存储所有待离散化的值
|
|
|
for (int i = 0; i < vec.size(); i++)
|
|
|
for (int j = i + 1; j < vec.size(); j++)
|
|
|
if (vec[j].y >= vec[i].y) alls.push_back(i), alls.push_back(j);
|
|
|
|
|
|
// 将所有值排序
|
|
|
sort(alls.begin(), alls.end());
|
|
|
// 去掉重复元素
|
|
|
alls.erase(unique(alls.begin(), alls.end()), alls.end());
|
|
|
|
|
|
// 重新捋着建边，通过二分查找，找出新的序号，这样就可以使用i<=alls.size()了！
|
|
|
for (int i = 0; i < vec.size(); i++)
|
|
|
for (int j = i + 1; j < vec.size(); j++)
|
|
|
if (vec[j].y >= vec[i].y) {
|
|
|
int x = lower_bound(alls.begin(), alls.end(), i) - alls.begin();
|
|
|
int y = lower_bound(alls.begin(), alls.end(), j) - alls.begin();
|
|
|
add(x, y);
|
|
|
}
|
|
|
|
|
|
int res = 0;
|
|
|
|
|
|
for (int i = 0; i < alls.size(); i++) {
|
|
|
// 最开始黄海SB的以为二分后，这里可以使用i<idx做为终止条件，其实是SB到家了！idx是边数，是边数，是边数！
|
|
|
// 不是点数，不是点数，不是点数！
|
|
|
memset(st, 0, sizeof st);
|
|
|
if (dfs(i)) res++;
|
|
|
}
|
|
|
|
|
|
printf("%d\n", vec.size() - res);
|
|
|
}
|
|
|
return 0;
|
|
|
} |
