题解分享
题解分享简介
平面切分(编程题) - 题解
```cpp
// https://dashoj.com/d/lqbproblem/p/108
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> PLL;
typedef pair<double, double> PDD;
set<PLL> spll;
ll n, ans = 1;
int main() { // y = a * x + b;
cin >> n;
while (n--) {
ll a, b;
cin >> a >> b;
if (spll.find({a, b}) != spll.end()) continue; // 重复线不计算
set<PDD> spdd;
for (auto &it: spll) {
double x = (it.second - b) * 1.0 / (a - it.first);
double y = a * x + b;
if (a == it.first || spdd.find({x, y}) != spdd.end()) continue;
spdd.insert({x, y});
}
ans += spdd.size() + 1;
spll.insert({a, b});
}
cout << ans << endl;
return 0;
}
// a1 * x + b1 == a2 * x + b2
// x == (b2 - b1) / (a1 - a2)
```
查看全文
0
0
2
3
