只AC了前两个点,求大佬解答
查看原帖
只AC了前两个点,求大佬解答
493444
对我而言就像楼主2021/4/14 21:26
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<stack>
#include<queue>
using namespace std;
struct dot {
	double x;
	double y;
	double operator^(const dot& a) {
		return x * a.y - y * a.x;
	}
	double operator*(const dot& a) {
		return a.x * x + a.y * y;
	}
	dot operator+(const dot& a) {
		return{ a.x + x,a.y + y };
	}
	dot operator-(const dot& a) {
		return{ a.x - x,a.y - y };
	}
	bool operator<(const dot& a)const{
		return x!=a.x?x<a.x:y<a.y;
	}
	bool operator>(const dot& a)const{
		return x!=a.x?x>a.x:y>a.y;
	}
};
double getdis(dot a, dot b) {
	dot tar = a - b;
	return sqrt((a-b)*(a-b));
}
double getdir(dot a, dot b, dot c) {
	dot ab = b - a;
	dot ac = c - a;
	return ab^ac;
}
int main(){
	int n;
	scanf("%d",&n);
	vector<dot> dots;
	for (int i = 0; i < n; i++) {
		double x, y;
		scanf("%lf%lf", &x, &y);
		dots.push_back({ x,y });
	}
	int len = dots.size();
	sort(dots.begin(),dots.end());
	stack<dot> down;
	stack<dot> up;
	down.push(dots[0]);
	down.push(dots[1]);
	for (int i = 2; i < len; i++) {
		dot b = down.top();
		down.pop();
		dot a = down.top();
		if (getdir(a, b, dots[i]) <= 0) {
			
			down.push(dots[i]);
		}
		else {
			down.push(b);
			down.push(dots[i]);
		}
		
	}


	up.push(dots[len - 1]);
	up.push(dots[len - 2]);
	for (int i = len - 3; i >= 0; i--) {
			dot b = up.top();
			up.pop();
			dot a = up.top();
			if (getdir(a, b, dots[i]) <= 0) {
				
				up.push(dots[i]);
			}
			else {
				up.push(b);
				up.push(dots[i]);
			}

	}
	double sum1 = 0, sum2 = 0;
	while (!down.empty()) {
		dot now = down.top();
		down.pop();
		if (down.empty()) break;
		dot next = down.top();
		sum1 += getdis(now, next);
	}
	while (!up.empty()) {
		dot now = up.top();
		up.pop();
		if (up.empty()) break;
		dot next = up.top();
		sum2 += getdis(now, next);
	}
	printf("%.2f\n", sum1 +sum2);
	
}
2021/4/14 21:26
加载中...