原题链接
这是一题思维要求较高的图论问题。
题意:
给你二维平面上n个点,每次操作必须满足如下条件
问你最多能删除多少点,并且输出删除的点对顺序。
思路:
首先这个题给我们点的坐标是以分数形式给出的,这就提示我们可以用分数来表示斜率。
假设当前输入的是 a, b, c, d, 即 x = a / b, y = c / d, 我们可以将斜率(未移动)表示为 {a * d, b * c}
加上移动操作,和化简,就有了代码中所示的
然后我们将每个斜率看作点,每个点看作边进行建图,此时问题就变成了在一个图上,
求每两条边共用一个点的最大边配对数量(边不可重复使用)
这个问题dfs就能解决,写法见如下代码
代码如下
int n, cnt;
ll a[N], b[N], c[N], d[N];
int h[M], e[M * 2], ne[M * 2], w[M * 2], idx;
bool vis[M], used[N];
vector<ll> ans[M];
map<pll, int> mp; // pll用来表示斜率 后面的 int 表示斜率编号
ll gcd(ll a, ll b)
{
return b ? gcd(b, a % b) : a;
}
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
bool dfs(int u, int fav = -1) // u 当前是哪个点,fav 表示从哪条边过来的
{
vis[u] = true;
for(int i = h[u] ; ~i ; i = ne[i])
{
int j = e[i], id = w[i]; // id 表示该边的编号
if(id != fav && !used[id]) //如果当前不是过来的边,并且该边没用过
{
if(vis[j]) //如果该点已经被访问过
ans[u].push_back(id), used[id] = true;
else
{
bool use = dfs(j, id);
//如果儿子没有使用这条边
if(!use) ans[u].push_back(id), used[id] = true;
}
}
}
//如果该结点使用了奇数条边
if(ans[u].size() % 2)
{
if(fav != -1 && !used[fav]) //如果有过来的边可用,就用它
{
ans[u].push_back(fav), used[fav] = true;
return true;
} //否则儿子里最后一条使用的边无法配对
else ans[u].pop_back();
}
return false;
}
int main()
{
IOS;
cin >> n;
for(int i = 1 ; i <= n ; ++ i)
{
cin >> a[i] >> b[i] >> c[i] >> d[i];
ll x = a[i] * d[i], y = b[i] * c[i], w = b[i] * d[i]; // 通分
ll g1 = gcd(x + w, y);
ll g2 = gcd(x, y + w);
mp[{(x + w) / g1, y / g1}] = 0;
mp[{x / g2, (y + w) / g2}] = 0;
}
for(auto &x : mp) x.y = ++ cnt; //分配编号
memset(h, -1, sizeof h);
for(int i = 1 ; i <= n ; ++ i)
{
ll x = a[i] * d[i], y = b[i] * c[i], w = b[i] * d[i];
ll g1 = gcd(x + w, y);
ll g2 = gcd(x, y + w);
int u = mp[{(x + w) / g1, y / g1}];
int v = mp[{x / g2, (y + w) / g2}];
// u 与 v 是原来的斜率, 现在表示点, i是原图的点,现在表示边。
add(u, v, i);
add(v, u, i);
}
for(int i = 1 ; i <= cnt ; ++ i) if(!vis[i]) dfs(i);
int res = 0;
for(auto &x : ans) res += x.size() / 2;
cout << res << '\n';
for(auto &x : ans)
{
int len = x.size();
for(int i = 0 ; i < len ; i += 2)
cout << x[i] << ' ' << x[i + 1] << '\n';
}
return 0;
}