Graham #2WA 萌新求助
查看原帖
Graham #2WA 萌新求助
536562
Ayano_楼主2023/4/2 21:49

代码如下,求大佬指点。(WrongAnswer#2 91/100)

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

int n;
struct p{
	double x, y;
} s[100010], points[100010];

double check(p s1, p e1, p s2, p e2) {
	return (e1.x-s1.x)*(e2.y-s2.y) - (e1.y-s1.y)*(e2.x-s2.x);
}

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

bool cmp(p a, p b) {
	double tmp = check(points[1], a, points[1], b);
	if (tmp > 0) return 1;
	if (tmp == 0 && dis(points[0], a) < dis(points[0], b)) return 1;
	return 0;
}

int main() {
	scanf("%d", &n);
	double mid;
	for (int i = 1; i <= n; i++) {
		scanf("%lf%lf", &points[i].x, &points[i].y);
		if (i != 1 && points[i].y < points[1].y) {
			swap(points[1], points[i]);
		}
	}
	sort(points+2, points+n+1, cmp);
	int top = 1;
	s[1] = points[1];
	for (int i = 2; i <= n; i++) {
		while (top > 1 && check(s[top-1], s[top], s[top], points[i]) <= 0) {
			top--;
		}
		s[++top] = points[i];
	}
	s[top+1] = points[1];
	double ans = 0;
	for (int i = 1; i <= top; i++) ans += dis(s[i], s[i+1]);
	printf("%.2lf", ans);
}
2023/4/2 21:49
加载中...