求助,样例2和样例3过不去
查看原帖
求助,样例2和样例3过不去
759274
Stevehim楼主2023/9/13 14:35

想法是将每个信用卡的四个边界点求出来,求凸包之后再加上一个圆的周长

#include <bits/stdc++.h>
#define maxn 100010
#define double long double
#define eps 1e-7
using namespace std;
int n;
double a,b,rr;
const double pi = acos(-1);
struct node { //表示坐标点
	double x, y;
	node () {}
	node(double a, double b) : x(a), y(b) {}
	bool operator < (const node &a) const {
		if (fabs(x - a.x) > eps){
			if(x - a.x < 0) return true;
			else return false;
		} //先按照横坐标排序
		if(y < a.y) return true;
		else return false;
	}
	node operator - (const node &a) const {
		return node(x - a.x, y - a.y); //这里是返回向量
	}
} p[maxn], ps[maxn];

int cmp(double x) {
	if (fabs(x) < eps) return 0;
	return x > 0 ? 1 : -1;
}

double rtoa(double rad){
	//	cout << rad << ' ' << rad / pi * 180.0 << endl;
	return rad * 180.0 / pi;
}

double ator(double angle){
	return angle * pi / 180.0;
}


node change(double r,double alpha, double beta, double tx,double ty){ //某个点旋转
	return (node){r * cos(ator(alpha + beta)) + tx, r * sin(ator(alpha + beta)) + ty};
}

double dis(node a, node b) {
	return sqrt(abs(a.x - b.x) * abs(a.x - b.x) + abs(a.y - b.y) * abs(a.y - b.y));
}

double cp(node a, node b) { //叉积操作
	return a.x * b.y - a.y * b.x;
}

int andrew() {
	sort(p + 1, p + 1 + n);
//	puts("");
//	swap(p[1],p[3]);
//	swap(p[1],p[4]);
//	for(int i = 1; i <= n; i++){
//		printf("%Lf %Lf\n", p[i].x , p[i].y);
//	}
//	cout << n << endl;
	int len = 0;
	for (int i = 1; i <= n; i++) {
		while (len > 1 && cmp(cp(ps[len] - ps[len - 1], p[i] - ps[len - 1])) < 0)
			len--; //将向量进行比对
		ps[++len] = p[i];
	}
//	cout << len << endl;
	//因为比较的是要插的点和没插的点的向量
	int k = len;
	for (int i = n - 1; i >= 1; i--) { //再扫一遍
		while (len > k && cmp(cp(ps[len] - ps[len - 1], p[i] - ps[len - 1])) < 0)
			len--;
		ps[++len] = p[i];
	}
	return len;
}
double tx,ty,rad;
double angle[5];
int cnt = 0;
double c;
int main() {
	ios::sync_with_stdio(false);
	cin >> n;
	cin >> a >> b >> rr;
	a /= 2,b /= 2;
	angle[1] = rtoa(atan2(a , b));
	angle[2] = rtoa(atan2(a , -b));
//	cout << rtoa(atan(a  -b)) << endl;
	angle[3] = rtoa(atan2(-a , -b));
	angle[4] = rtoa(atan2(-a , b));
	c = sqrt(a * a + b * b) / 1.0; //倍数
	for(int i = 1; i <= n; i++){
		cin >> tx >> ty >> rad;
		for(int j = 1; j <= 4; j++){
//			cout << angle[j] << endl;
			p[++cnt] = change(c,  angle[j], rtoa(rad), tx, ty);
//			cout << p[cnt].x << ' ' << p[cnt].y << endl;
		}
	}
	n = cnt;
//	for(int i = 1; i <= n; i++){
//		cout << p[i].x << ' ' << p[i].y << endl;
//	}
	int tmp = andrew();
	double ans = 0;
//	cout << tmp  - 1 << endl;
	for(int i = 1; i < tmp - 1; i++){
		ans += dis(ps[i], ps[i + 1]);
	}
	ans += dis(ps[tmp - 1], ps[1]);
	ans += 2.0 * rr * pi;
	printf("%.2Lf", ans);
	return 0;
}
2023/9/13 14:35
加载中...