QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#439264 | #8768. Arrested Development | PetroTarnavskyi# | WA | 0ms | 4044kb | C++20 | 3.7kb | 2024-06-11 18:43:48 | 2024-06-11 18:43:48 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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'