A.选拔赛

把两个数组拍一下序之后发现 (a_x+c_y) 的和一共只有 (n^2) 个，那么离散下来枚举前 (k) 个和的最小值

设 calc(i,j) 表示前 (k) 个数的和最小值和后面的数的和的最大值

对于当前的最小值，每个 (ile k) 的 (a_i) 能选的 (c_y) 都是一个的后缀，得到这个后缀是 (trivial) 的

考虑这些后缀的长度是递减的，那么直接按照排序减掉前面的数量就行

设 (dp[i][j]) 表示前 (i) 个 (c_i) 中有 (j) 个被使用于前 (k) 个数

记录每个 (c_i) 在当前的 (i,j) 中可以在两边所取到的区间长度

这样分是不是加入前面 (k) 个数进行两种转移即可

B.跳跃

用线段树对 (iin [0,log n]) 维护每 (2^i) 步能到的区间

其实对于这个限制，如果存在 (i) 使得 ([r_i,n]) 有一个点的 (l_i>i) 那么就成立，对于左边也是一样的

使用前后缀进行优化

在从大到小维护答案是不是可以被插入时，可以按照建树的方法求当前待拓展的答案的线段树

这样的话总的复杂度是 (Theta(nlog^2n))

C.切蛋糕

考虑对所有直接求一个交集，再和原图形求一个交集

这个需要半平面交，剩下的按照极角排序之后在大力分类讨论扫一扫就行了

然而不会半平面交，只能打 (30') 的暴力

半平面交

平面上有一些凸多边形，求这些凸多边形的交（其实求出来并了以后周长和面积就可做了）

注意：叉积为 a.x*b.y-b.x*a.y 如果大于 (0) 说明两个向量成锐角，等于 (0) 表明垂直，小于 (0) 为钝角

那么做法如下：

先把第一个多边形当做 (bas)，对于新加入的每个多边形，依次加入所有边

加入边时枚举每个原来的边判断是不是有交点，如果有就求交点新加入直线

然后对于 (Theta(nlog n)) 的做法，先把所有线按照极角排序，然后维护一个单调队列

还是分割平面，考虑对于原答案的更改一定是一定是删掉极角最大或小的一些区间，那么直接弹就好了

然后得到这个做法之后，为了避免分类讨论，我们把整个圆分成 (k) 个，把这些段弧当做直线考虑

然后一起做半平面交，把弧上的边打上标记

注意，使用结构体函数的时候会直接给 (fl) 一个随机值，记得重置


#include<bits/stdc++.h>
using namespace std;
#define int long long
#define reg register
#define For(i,a,b) for(reg int i=a;i<=b;++i)
#define Down(i,a,b) for(reg int i=a;i>=b;--i)
inline int max(int x,int y){return x>y?x:y;}
inline int min(int x,int y){return x<y?x:y;}
inline void swap(int &x,int &y){int t=x; x=y; y=t; return ;}
namespace yspm{
	inline int read(){
		int res=0,f=1; char k;
		while(!isdigit(k=getchar())) if(k=='-') f=-1;
		while(isdigit(k)) res=res*10+k-'0',k=getchar();
		return res*f;
	}
	const int N=100010;
	const double pi=acos(-1);
	struct node{
		double x,y;
		node(){}
		node(double xx,double yy){x=xx; y=yy; return ;}
		node operator +(const node &a)const{return node(x+a.x,y+a.y);}
		node operator -(const node &a)const{return node(x-a.x,y-a.y);}
		node operator *(const node &a)const{return node(x*a.x-y*a.y,x*a.y+y*a.x);}
		inline double dist(){return sqrt(x*x+y*y);}
		node operator *(const double &a)const{return node(x*a,y*a);}
	}p[N];
	int k=10000,h=1,t,n,cnt; double R,ans[2];
	inline double cross(node a,node b){return a.x*b.y-a.y*b.x;}
	struct line{
		node st,ed; double ang;
		bool rnd;
		line(){}
		line(node a,node b){st=a; ed=b; ang=atan2(ed.y-st.y,ed.x-st.x); rnd=0; return ;}
		bool operator <(const line &a)const{return ang==a.ang?cross(ed-st,a.st-st)<0:ang<a.ang;}
	}l[N],q[N];
	inline node get(line a,line b){return a.st+(a.ed-a.st)*(cross(b.ed-b.st,b.st-a.st)/cross(b.ed-b.st,a.ed-a.st));}
	signed main(){
		freopen("cut.in","r",stdin); freopen("cut.out","w",stdout);
		n=read(); scanf("%lf
",&R);  
		for(reg int i=1;i<=n;++i){
			double a,h; scanf("%lf%lf",&a,&h);
			l[++cnt]=line(node(cos(a*pi/180),sin(a*pi/180))*h,node(cos(a*pi/180),sin(a*pi/180))*h+node(cos(a*pi/180+pi/2),sin(a*pi/180+pi/2))); q[i].rnd=0;
		}
		for(reg int i=0;i<k;++i) l[++cnt]=line(node(cos(pi*2/k*i),sin(pi*2/k*i))*R,node(cos(pi*2/k*(i+1)),sin(pi*2/k*(i+1)))*R),l[cnt].rnd=1; sort(l+1,l+cnt+1);
		for(reg int i=1;i<=cnt;++i){
			if(i!=1&&l[i].ang==l[i-1].ang) continue; 
			while(h<t&&cross(l[i].ed-l[i].st,p[t-1]-l[i].st)<0) --t; 
			while(h<t&&cross(l[i].ed-l[i].st,p[h]-l[i].st)<0) ++h; 
			q[++t]=l[i];
			if(h<t) p[t-1]=get(q[t-1],q[t]);
  		} 
		while(h<t&&cross(q[h].ed-q[h].st,p[t-1]-q[h].st)<0) --t; 
		p[t]=get(q[h],q[t]); p[h-1]=p[t];
		for(reg int i=h;i<=t;++i)if(q[i].rnd) ans[1]+=(p[i-1]-p[i]).dist(); else ans[0]+=(p[i-1]-p[i]).dist();
		printf("%.10lf %.10lf
",ans[0],ans[1]);
		return 0;
	}
}
signed main(){return yspm::main();}

恶心吗？不恶心。不恶心吗？恶心。( exttt{That's true Polygen.})