Graham #2WA 求助
查看原帖
Graham #2WA 求助
409265
YJY0807qwq楼主2022/12/5 08:32
#include <bits/stdc++.h>
using namespace std;
int n, cnt = 1;
double ans;
struct Point
{
    double x, y;
} points[100005], pstack[100005];
double dist(Point a, Point b)
{
	return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
double cross(Point a1, Point a2, Point b1, Point b2)
{
	return (a2.x - a1.x) * (b2.y - b1.y) - (b2.x - b1.x) * (a2.y - a1.y);
}
bool cmp(Point a, Point b)
{
	if (cross(points[1], a, points[1], b) > 0)
	{
		return 1;
	}
	if (cross(points[1], a, points[1], b) == 0 && dist({0, 0}, a) < dist({0, 0}, b))
	{
		return 1;
	}
	return 0;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> points[i].x >> points[i].y;
        if (i != 1 && points[i].y < points[1].y)
        {
            swap(points[i], points[1]);
        }
    }
    sort(points + 2, points + n + 1, cmp);
//	for (int i = 1; i <= n; i++)
//	{
//		cout << points[i].x << ' ' << points[i].y << endl;
//	}
	pstack[1] = points[1];
	for (int i = 2; i <= n; i++)
	{
		while (cnt > 1 && cross(pstack[cnt - 1], pstack[cnt], pstack[cnt], points[i]) <= 0)
		{
			cnt--;
		}
		pstack[++cnt] = points[i];
	}
	pstack[cnt + 1] = points[1];
	for (int i = 1; i <= cnt; i++)
	{
//		cout << pstack[i].x << ' ' << pstack[i].y << endl;
		ans += dist(pstack[i], pstack[i + 1]);
	}
	cout << fixed << setprecision(2) << ans;
}
2022/12/5 08:32
加载中...