QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#368907#8507. Clever Cell ChoicesPetroTarnavskyi#RE 0ms0kbC++202.7kb2024-03-27 17:56:232024-03-27 17:56:24

Judging History

你现在查看的是最新测评结果

  • [2024-03-27 17:56:24]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-03-27 17:56:23]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second 

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

const db EPS = 1e-6;

db inter(int k0, int b0, int k1, int b1)
{
	if(k0 == k1)
		return -1e9;
	//k0 * x + b0 = k1 * x + b1;
	//x(k1 - k0) = b0 - b1;
	
	return 1.0 * (b0 - b1) / (k1 - k0);
}

vector<tuple<db, int, int>> convex(vector<pair<int, int>> lines)
{
	//lines.F * x + lines.S
	sort(ALL(lines));
	
	vector<tuple<db, int, int>> res;
	res.PB({0, lines[0].F, lines[0].S});
	
	FOR(i, 1, SZ(lines))
	{
		db x = 0;
		while(SZ(res))
		{
			auto [prevX, k0, b0] = res.back();
			x = inter(k0, b0, lines[i].F, lines[i].S);
			
			if(x - EPS < prevX)
				res.pop_back();
			else
				break;
		}
		res.PB({max(0.0, x), lines[i].F, lines[i].S});
	}
	
	return res;
}

vector<tuple<db, int, int, int>> solve(vector<PII> lines, int t)
{
	auto res1 = convex(lines);
	FOR(i, 0, SZ(lines))
	{
		lines[i].F *= -1;
		lines[i].S *= -1;
	}
	auto res2 = convex(lines);
	
	int i = 0, j = 0;
	
	vector<tuple<db, int, int, int>> res;
	int k = get<1>(res1[0]) + get<2>(res2[0]);
	int b = get<1>(res1[0]) + get<2>(res2[0]);
	res.PB({0, t, k, b});
	
	while(i + 1 < SZ(res1) || j + 1 < SZ(res2))
	{
		db x;
		if((j + 1 == SZ(res2)) || (i + 1 < SZ(res1) && get<0>(res1[i + 1]) < get<0>(res2[j + 1])))
		{
			x = get<0>(res1[i + 1]);
			k += get<1>(res1[i + 1]) - get<1>(res1[i]);
			b += get<2>(res1[i + 1]) - get<2>(res1[i]);
			i++;
		} 
		else
		{
			x = get<0>(res2[j + 1]);
			k += get<1>(res2[j + 1]) - get<1>(res2[j]);
			b += get<2>(res2[j + 1]) - get<2>(res2[j]);	
			j++;
		}
		res.PB({x, t, k, b});
	}
	return res;
}

int a[2], b[2];
pair<db, db> find(db l, db r)
{
	
}


int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	vector<PII> x(n), y(n);
	FOR(i, 0, n)
	{
		cin >> x[i].S >> y[i].S >> x[i].F >> y[i].F;
	}
	
	auto resX = solve(x, 0);
	auto resY = solve(y, 1);
	a[0] = get<1>(resX[0]);
	b[0] = get<2>(resX[0]);
	a[1] = get<1>(resY[0]);
	b[1] = get<2>(resY[0]);
	
	
	auto res = resX;
	res.insert(res.end(), ALL(resY));
	sort(ALL(res));
	
	pair<db, db> ans = find(0, 0);
	FOR(i, 0, SZ(res))
	{
		auto [l, t, ks, bs] = res[i];
		a[t] = ks;
		b[t] = bs;
		
		db r = (i + 1 == SZ(res) ? 1e10 : get<0>(res[i + 1]));
		
		auto cur = find(l, r);
		
		if(ans.F - EPS < cur.F)
			ans = cur;
	}
	cout << fixed << setprecision(10) << ans.S << "\n";
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Runtime Error

input:

3 3
#.#
...
#.#

output:


result: