1 条题解

  • 0
    @ 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
    上传者