[Kubic] Lines
2021/11/13 23:09:53
本文主要是介绍[Kubic] Lines,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目大意
给定 \(n\) 条解析式为 \(ax+by+c=0\) 的直线,选出最少的直线去覆盖所有交点。
解题思路
显然,没有删掉的直线一定是互相平行的,否则一定有至少一个交点没有被删掉。
所以其实就是要选出最多的直线使它们两两平行。
对于每一条直线暴力找出有多少条直线与它平行,取最大值即可。
用 unordered_map
维护,时间复杂度 \(\mathcal O(n \log n)\)。
CODE
#include <bits/stdc++.h> using namespace std; #define int long long inline int read() { int x = 0, f = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); } while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); } return x * f; } int n; int a[100007], b[100007], c; map<pair<int, int>, int> mp; int ans; int A, B; signed main() { n = read(); for (int i = 1; i <= n; ++i) { a[i] = read(), b[i] = read(), c = read(); mp[make_pair(a[i], b[i])]++; if (a[i] == 0) A++; if (b[i] == 0) B++; } if (A + B == n) { cout << min(A, B) << "\n"; return 0; } for (int i = 1; i <= n; ++i) ans = max(ans, mp[make_pair(a[i], b[i])]); cout << n - ans << "\n"; return 0; }
这篇关于[Kubic] Lines的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-29易优CMS安装常见问题汇总-icode9专业技术文章分享
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享
- 2024-06-28忘记eyoucms后台密码怎么办?-icode9专业技术文章分享
- 2024-06-26终极指南:Scrum中如何设置需求优先级
- 2024-06-26AI大模型企业应用实战(25)-为Langchain Agent添加记忆功能
- 2024-06-26小白家庭 nas 搭建方案-icode9专业技术文章分享
- 2024-06-23AI大模型企业应用实战(14)-langchain的Embedding
- 2024-06-23AI大模型企业应用实战(15)-langchain核心组件
- 2024-06-23AI大模型企业应用实战(16)-langchain核心组件
- 2024-06-23AI 大模型企业应用实战(06)-初识LangChain