Cod sursa(job #2848707)

Utilizator Radu_marioRadu Mario Radu_mario Data 13 februarie 2022 09:38:32
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 kb
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;

ifstream file_in("infasuratoare.in");
ofstream file_out("infasuratoare.out");

int i;
bool C[120005];

struct Point
{ double X, Y; }
P[120005] = { 1000000005 };

vector<int> ConvexHull;

int main()
{
	int N; file_in >> N;
	for (i = 1; i <= N; ++i)
		file_in >> P[i].X >> P[i].Y;

	int InitPoint = 0;
	for (i = 1; i <= N; ++i)
		if (P[i].X < P[InitPoint].X) InitPoint = i;

	int CurrentPoint = InitPoint, NewPoint;
	double TempPoint, Angle, LastPoint = 0;
	bool FirstPoint = true;
	
	while (FirstPoint || InitPoint != CurrentPoint)
	{
		NewPoint = CurrentPoint;
		FirstPoint = false;
		TempPoint = 365;
		
		ConvexHull.push_back(CurrentPoint);
		for (i = 1; i <= N; ++i)
		{
			if (C[i] || i == CurrentPoint) continue;
			Angle = atan2(P[i].X - P[CurrentPoint].X, P[i].Y - P[CurrentPoint].Y);

			if (Angle < 0) Angle += 2 * M_PI;
			Angle -= LastPoint;
			if (Angle < 0) Angle += 2 * M_PI;

			if (Angle < TempPoint) 
				TempPoint = Angle, NewPoint = i;
		}

		LastPoint = atan2(-(P[CurrentPoint].X - P[NewPoint].X), -(P[CurrentPoint].Y - P[NewPoint].Y));
		if (LastPoint < 0) LastPoint += 2 * M_PI;

		CurrentPoint = NewPoint;
		C[CurrentPoint] = true;
	}

	reverse(ConvexHull.begin(), ConvexHull.end());
	file_out << ConvexHull.size() << '\n';

	for (i = 0; i < ConvexHull.size(); ++i)
		file_out << P[ConvexHull[i]].X << ' ' << P[ConvexHull[i]].Y << '\n';

	return 0;
}