Cod sursa(job #2659562)

Utilizator altcontnoualt cont altcontnou Data 17 octombrie 2020 08:24:58
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.4 kb
#include<stdio.h>

#include<vector>

#include<math.h>

#include <algorithm>

#define pb push_back



const int maxn = 120000;



using namespace std;



vector<int> VECT;

double X[maxn],Y[maxn];

int N,VER[maxn];



int main()

{

	freopen("infasuratoare.in","r",stdin);

	freopen("infasuratoare.out","w",stdout);

	scanf("%d\n",&N);

	X[0] = 1000000000;Y[0] = 1000000000;

	for(int i = 1;i <= N; ++i)

		scanf("%lf %lf\n",&X[i],&Y[i]);

	int punct_initial = 0;

	int cur = 0;

	int move = 1;

	for(int i = 1;i <= N; ++i)

		if (X[i] < X[punct_initial]) punct_initial = i;

	cur = punct_initial;

	double last = 0;

	while(move || punct_initial != cur)

	{

		move = 0;

		VECT.pb(cur);

		double ma = 10000;

		int poznoua = cur;

		for(int i = 1;i <= N; ++i)

		{

			if (VER[i] || i == cur) continue;

			double unghi = atan2((X[i] - X[cur]),Y[i] - Y[cur]);

			if (unghi < 0) unghi += 2* M_PI;

			unghi -= last;

			if (unghi < 0) unghi += 2 * M_PI;

			if (ma > unghi) {ma = unghi; poznoua = i;}

		}

		last = atan2(-(X[cur] - X[poznoua]),-(Y[cur] - Y[poznoua]));

		if (last < 0) last += 2 * M_PI;

		cur = poznoua;

		VER[cur] = 1;

	}

	reverse(VECT.begin(),VECT.end());

	printf("%d\n",VECT.size());

	for(unsigned int i = 0;i < VECT.size(); ++i)

		printf("%lf %lf\n",X[VECT[i]],Y[VECT[i]]);

	return 0;

}