chyx's Blog

循环数组的处理

int mk[1024];
ll arr[2048];

	int period, pre;
	arr[0] = A;
	for(int i = 1; ; ++i){
		arr[i] = a * arr[i-1] * arr[i-1] % M + b * arr[i-1] + c;
		arr[i] %= M;
		if( mk[ arr[i] ] ){
			pre = mk[arr[i]];
			period = i - pre;
			break;
		}
		mk[ arr[i] ] = i;
	}

归并排序，顺便求逆序数

void merge_sort( int* v, int n){
	if( n < 20 ) Rep(__, n) Rep(i,n-1)if( v[i] > v[i+1] ) swap( v[i], v[i+1]), cnt++;
	if( n < 20 ) return;
	merge_sort(v, n/2);
	merge_sort(v+n/2, (n+1)/2);
	int l = 0, r = n/2;
	for(int i = 0; i<n ; ++i){
		if(r == n || l != n/2 && v[l] <= v[r] ) tmp[i] = v[l++] ;
		else tmp[i] = v[r], cnt += r - i, r++;
	}
//	Rep(i,n) cout << tmp[i] << " "; cout << endl;
	copy( tmp, tmp + n, v);
}

两圆相交求并

double inter_circle( double x1, double y1, double r1, double x2, double y2, double r2){
	double d = sqrt(sq(x1-x2)+sq(x2-y2));
	if( d >= r1 + r2 ) return pi*(r1*r1+r2*r2);
	if( d <= abs(r1-r2) || abs(d) < 1e-8) return pi*max( r1*r1, r2*r2);
	double t1 = acos(( d*d + r1*r1 - r2*r2) / 2 / d / r1);
	double t2 = acos(( d*d + r2*r2 - r1*r1) / 2 / d / r2);
	double area = r1*r1*pi + r2*r2*pi;
	area -= t1 * r1 * r1;
	area -= t2 * r2 * r2;
	double s = (r1 + r2 + d)/2;
	area += 2 * sqrt( s * (s-r1) * (s-r2) * (s-d));
	return area;
}

两球相交求并

double inter_ball( double r1,double r2, double d){
	if( d >= r1 + r2 ) return 0;
	if( d <= abs(r1-r2) || abs(d) < 1e-8) return pi*min( r1*r1, r2*r2);
	double p = (r1 + r2 + d)/2;
	double tri = sqrt( p * (p-r1) * (p-r2) * (p-d));
	double r = tri / d * 2; 
	double h1 = sqrt( sq(r1-r) );
	double h2 = sqrt( sq(r2-r) );
	double s = pi*r*r;
	double area = h1 * s / 3 + h2 * s / 3;
	double x1 = (d*d+r1*r1-r2*r2)/2/d - d;
	double x2 = (d*d+r2*r2-r1*r1)/2/d - d;
	area = pi * ( r1*r1*(r1-x1) - ( r1*r1*r1 - x1*x1*x1)/3);
	area += pi * ( r2*r2*(r2-x2) - ( r2*r2*r2 - x2*x2*x2)/3);
	return area;