路过dalao帮孩子调调吧,都弄两天了
查看原帖
路过dalao帮孩子调调吧,都弄两天了
519384
Link_Cut_Y楼主2022/3/7 21:54
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>

#define x first
#define y second

using namespace std;

typedef pair<double, double> PDD;
const double eps = 1e-8;
const int N = 1010;

int n;
PDD q[N];
int path[N];
bool st[N];
int cnt = 0;

// Operator Defining

PDD operator - (PDD a, PDD b)
{
	return {a.x - b.x, a.y - b.y};
}

bool operator == (PDD a, PDD b)
{
	return a.x == b.x && a.y == b.y;
}

PDD operator + (PDD a, PDD b)
{
	return {a.x + b.x, a.y + b.y};
}

PDD operator * (PDD a, double b)
{
	return {a.x * b, a.y * b};
}

PDD operator / (PDD a, double b)
{
	return {a.x / b, a.y / b};
}

// Functions

double cross(PDD a, PDD b)
{
	return a.x * b.y - a.y * b.x;
}

double dot(PDD a, PDD b)
{
	return a.x * b.x + a.y * b.y;
}

double area(PDD a, PDD b, PDD c)
{
	return cross(b - a, c - a);
}

double get_length(PDD a)
{
	return dot(a, a);
}

double get_dist(PDD a, PDD b)
{
    double dx = a.x - b.x, dy = a.y - b.y;
    return sqrt(dx * dx + dy * dy);
}

double get_angle(PDD A, PDD B, PDD C)
{
    double a = get_dist(A, B);
    double b = get_dist(B, C);
    double c = get_dist(C, A);
    
    // printf("%.2lf %.2lf %.2lf", a, b, c);
	double res = acos((a * a + b * b - c * c) / (2 * a * b));
	
	return res;
}

int cmp(double a, double b)
{
	return fabs(a - b) < eps ? 0 : ((a - b) > 0 ? 1 : -1);
}

void work()
{
	int start = 1;
	
	// Found The Start
	
	for (int i = 1; i <= n; i ++ )
		if (q[i].y < q[start].y) start = i;
		else if (q[i].y == q[start].y && q[i].x < q[start].x) start = i;
		
	// Work
	
	q[0] = {0, q[start].y};
	path[ ++ cnt] = start;
	
	st[start] = true;
	st[0] = true;
	
	while (cnt != n)
	{
		int next = 0;
		double max_angle = 0;
		for (int i = 1; i <= n; i ++ )
		{
			if (st[i]) continue;
			if (area(q[path[cnt - 1]], q[path[cnt]], q[i]) < 0) continue;
			
			if (get_angle(q[path[cnt - 1]], q[path[cnt]], q[i]) > max_angle)
				max_angle = get_angle(q[path[cnt - 1]], q[path[cnt]], q[i]), next = i;
		}
		
		st[next] = true;
		path[ ++ cnt] = next;
	}
}

int main()
{
	scanf("%d", &n);
	
	for (int i = 1; i <= n; i ++ )
		scanf("%lf%lf", &q[i].x, &q[i].y);
		
	work();
	
	printf("%d ", cnt);
	for (int i = 1; i <= cnt; i ++ ) printf("%d ", path[i]);
	
	return 0;
}
2022/3/7 21:54
加载中...