QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#439264#8768. Arrested DevelopmentPetroTarnavskyi#WA 0ms4044kbC++203.7kb2024-06-11 18:43:482024-06-11 18:43:48

Judging History

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

  • [2024-06-11 18:43:48]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:4044kb
  • [2024-06-11 18:43:48]
  • 提交

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 int N = 3007;

int n, w;
int xs[N], ys[N][2];

bool checkInfinity()
{
	vector<PII> segments;
	FOR(i, 0, n)
	{
		segments.PB({ys[i][0], ys[i][1]});
	}
	sort(ALL(segments));
	int r = segments[0].S;
	FOR(i, 0, n)
	{
		if (i > 0 && r < segments[i].F)
			return false;
		r = max(r, segments[i].S);
	}
	return true;
}

pair<db, db> findShade(db x, int i)
{
	db z[2];
	FOR(j, 0, 2)
	{
		z[j] = (w - x) / (xs[i] - x) * ys[i][j];
	}
	return {z[0], z[1]};
}

db inter(db x1, db y1, db x2, db y2)
{
	return y1 * (x1 - x2) / (y2 - y1) + x1;
}

#warning EPS
bool interSegments(pair<db, db> s1, pair<db, db> s2)
{
	return max(s1.F, s2.F) <= min(s1.S, s2.S);
}

vector<db> globalVec = {0};
vector<PII> rollback;
db ans = 0;

struct DSU
{
	int n;
	VI p, sz;
	void init(int _n)
	{
		n = _n;
		p.resize(n);
		iota(ALL(p), 0);
		sz.assign(n, 1);
	}
	int find(int v)
	{
		if (v == p[v])
			return v;
		return find(p[v]);
	}
	bool unite(int u, int v)
	{
		u = find(u);
		v = find(v);
		if (u == v)
			return false;
		if (sz[u] > sz[v])
			swap(u, v);
		p[u] = v;
		sz[v] += sz[u];
		rollback.PB({u, v});
		return true;
	}
} dsu;

struct SegTree
{
	int n;
	vector<vector<PII>> t;
	void init(int _n)
	{
		n = 1;
		while (n < _n)
			n *= 2;
		t.resize(2 * n - 1);
	}
	void upd(int v, int tl, int tr, int l, int r, const PII& edge)
	{
		if (r <= tl || tr <= l)
			return;
		if (l <= tl && tr <= r)
		{
			t[v].PB(edge);
			return;
		}
		int tm = (tl + tr) / 2;
		upd(2 * v + 1, tl, tm, l, r, edge);
		upd(2 * v + 2, tm, tr, l, r, edge);
	}
	void traverse(int v, int tl, int tr)
	{
		int szRollback = SZ(rollback);
		for (auto [i, j] : t[v])
		{
			dsu.unite(i, j);
		}
		if (tr - tl == 1)
		{
			if (dsu.sz[dsu.find(0)] == n)
			{
				ans += globalVec[tl + 1] - globalVec[tl];
			}
		}
		else
		{
			int tm = (tl + tr) / 2;
			traverse(2 * v + 1, tl, tm);
			traverse(2 * v + 2, tm, tr);
		}
		while (SZ(rollback) > szRollback)
		{
			auto [i, j] = rollback.back();
			rollback.pop_back();
			dsu.p[i] = i;
			dsu.sz[j] -= dsu.sz[i];
		}
	}
} st;


int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(10);
	cin >> n >> w;
	FOR(i, 0, n)
		cin >> xs[i] >> ys[i][0] >> ys[i][1];
	if (checkInfinity())
	{
		cout << "-1\n";
		return 0;
	}
	vector<tuple<int, int, db, db>> edgesAlive;
	FOR(i, 0, n)
	{
		FOR(j, i + 1, n)
		{
			vector<db> vec = {0};
			FOR(ii, 0, 2)
			{
				FOR(jj, 0, 2)
				{
					if (ys[i][ii] != ys[j][jj])
					{
						db x = inter(xs[i], ys[i][ii], xs[j], ys[j][jj]);
						if (x < 0)
							vec.PB(x);
					}
				}
			}
			sort(ALL(vec));
			FOR(k, 0, SZ(vec) - 1)
			{
				db x = (vec[k] + vec[k + 1]) / 2;
				auto s1 = findShade(x, i), s2 = findShade(x, j);
				if (interSegments(s1, s2))
				{
					edgesAlive.PB({i, j, vec[k], vec[k + 1]});
				}
			}
			globalVec.insert(globalVec.end(), ALL(vec));
		}
	}
	sort(ALL(globalVec));
	st.init(SZ(globalVec) - 1);
	for (auto [i, j, l, r] : edgesAlive)
	{
		int idxL = lower_bound(ALL(globalVec), l) - globalVec.begin();
		int idxR = lower_bound(ALL(globalVec), r) - globalVec.begin();
		st.upd(0, 0, st.n, idxL, idxR, {i, j});
	}
	dsu.init(n);
	st.traverse(0, 0, st.n);
	cout << ans << "\n";
	return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 4044kb

input:

4
100 1
1 90
1 20
1 20

output:

0.0000000000

result:

wrong answer 1st lines differ - expected: '3', found: '0.0000000000'