返回题解分享
讨论 / 题解分享/ 帖子详情

平面切分(编程题) - 题解

// 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 喜欢 2 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!