1 条题解
-
0117爱好者 (mengqingyu) LV 10 @ 2024-9-27 18:19:56
#include<bits/stdc++.h> using namespace std; int n, cont = 0; double a, b, c, d;; map<int, double> raw; map<double, int> val; vector<pair<double, pair<pair<double, double>, int> > > v;//横坐标,两纵,增减 set<double> s; struct node { double len; int cnt; }t[20020 << 2]; void init() { raw.clear(); val.clear(); v.clear(); s.clear(); } void build(int p, int l, int r)//后期发现其实根本就不用build,反正本来也都是0 —_—' { t[p].len = t[p].cnt = 0; if(l == r) { return ; } int mid = l + r >> 1; build(p * 2 , l, mid); build(p * 2 + 1, mid + 1, r); } void update(int p, int l, int r, int ls, int rs, int k) { if(ls <= l && r <= rs) { t[p].cnt += k; t[p].len = t[p].cnt > 0 ? raw[r + 1] - raw[l] : t[p * 2 + 1].len + t[p * 2].len ;//层数决定长度 return ; } int mid = l + r >> 1; if(ls <= mid) update(p * 2, l, mid, ls, rs, k); if(rs > mid) update(p * 2 + 1, mid + 1, r, ls, rs, k); t[p].len = t[p].cnt > 0 ? raw[r + 1] - raw[l] : t[p * 2].len + t[p * 2 + 1].len; return ;//和上面一样 } int main() { while(1) { scanf("%d", &n); if(!n) return 0; init();//一定要初始化 for(int i = 1; i <= n; i++) { scanf("%lf%lf%lf%lf", &a, &b, &c, &d); v.push_back(make_pair(a, make_pair(make_pair(b, d), 1))); v.push_back(make_pair(c, make_pair(make_pair(b, d), -1))); s.insert(b);//存入涉及到的高度,set会自动排序去重 s.insert(d); } sort(v.begin(), v.end()); int rk = 0; for(set<double> ::iterator it = s.begin(); it != s.end(); it++) { val[(*it)] = ++rk;//存储映射 raw[rk] = (*it);//反函数 } build(1, 1, rk - 1);//以区间为边界,所以建树范围是(1, rk - 1) double ans = 0.0, now = 0; for(int i = 0; i < v.size(); i++)//开始扫描 { ans += (v[i].first - now) * t[1].len; update(1, 1, rk - 1, val[v[i].second.first.first], val[v[i].second.first.second] - 1, v[i].second.second);//看起来复杂,其实好理解 now = v[i].first;//实时更新 } printf("Test case #%d\nTotal explored area: %.2lf\n\n", ++cont, ans); } }
- 1
信息
- ID
- 158
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 8
- 标签
- 递交数
- 21
- 已通过
- 6
- 上传者