【bzoj4418】[Shoi2013]扇形面积并扫描线+线段树

- 日理万妓 2021-10-01 01:54 248阅读 0赞

题目描述

给定N个同心的扇形，求有多少面积，被至少K个扇形所覆盖。

输入

第一行是三个整数n，m，k。n代表同心扇形的个数，m用来等分 \[-π,π\]的弧度。

从第二行开始的n行，每行三个整数r，a1，a2。描述了一个圆心在原点的扇形，半径为r，圆心角是从弧度πa1/m到πa2/m，a1可能大于a2，逆时针扫过的区域为该扇形面积。

输出

输出一个整数ans，至少被K个扇形所覆盖的总面积等于π/2m×ans

保证答案不超过2^63-1

样例输入

【输入样例1】  
3 8 2  
1 -8 8  
3 -7 3  
5 -5 5  
【输入样例2】  
2 4 1  
4 4 2  
1 -4 4

样例输出

【输出样例1】  
76  
【输出样例2】  
98

--------------------

题解

扫描线+线段树

把每个扇形拆成：a1时刻加入扇形，a2时刻删除扇形。

那么把所有这样的边放到一起，按照出现位置排序。

然后问题转化为：前缀+1，前缀-1，查询值大于等于k的位置个数。容易发现数值是单调的，因此可以使用线段树维护修改，然后在线段树上二分解决问题。具体实现上，可以使用差分带点修改来代替区间修改。

时间复杂度 $O(n\\log n)$

注意一下a1>a2时要拆成两个扇形（a1~m、-m~a2）解决。

#include <cstdio>
    #include <algorithm>
    #define N 100010
    #define lson l , mid , x << 1
    #define rson mid + 1 , r , x << 1 | 1
    using namespace std;
    struct data
    {
    	int p , c , v;
    	data() {}
    	data(int P , int C , int V) {p = P , c = C , v = V;}
    	bool operator<(const data &a)const {return p < a.p;}
    }q[N << 2];
    int sum[N << 2] , tot;
    void update(int p , int a , int l , int r , int x)
    {
    	sum[x] += a;
    	if(l == r) return;
    	int mid = (l + r) >> 1;
    	if(p <= mid) update(p , a , lson);
    	else update(p , a , rson);
    }
    int query(int k , int l , int r , int x)
    {
    	if(l == r) return l;
    	int mid = (l + r) >> 1;
    	if(k < sum[x << 1]) return query(k , lson);
    	else return query(k - sum[x << 1] , rson);
    }
    int main()
    {
    	int n , m , k , i , a , b , r , last = 0 , now = 0;
    	long long ans = 0;
    	scanf("%d%d%d" , &n , &m , &k);
    	for(i = 1 ; i <= n ; i ++ )
    	{
    		scanf("%d%d%d" , &r , &a , &b);
    		if(a <= b) q[++tot] = data(a , r , 1) , q[++tot] = data(b , r , -1);
    		else q[++tot] = data(-m , r , 1) , q[++tot] = data(b , r , -1) , q[++tot] = data(a , r , 1) , q[++tot] = data(m , r , -1);
    	}
    	sort(q + 1 , q + tot + 1);
    	for(i = 1 ; i <= tot ; i ++ )
    	{
    		r = query(now - k , 1 , 100001 , 1) - 1 , ans += 1ll * r * r * (q[i].p - last);
    		now += q[i].v , update(q[i].c + 1 , q[i].v , 1 , 100001 , 1) , last = q[i].p;
    	}
    	printf("%lld\n" , ans);
    	return 0;
    }

转载于:https://www.cnblogs.com/GXZlegend/p/8010725.html