Cod sursa(job #2226051)

Utilizator l-teenLucian l-teen Data 29 iulie 2018 14:01:02
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include "stdio.h"
#include "math.h"
#define M_PI       3.14159265358979323846

int main()
{
	double points[120000][2], maxAngle, angle, lastAngle, dif_oriz = 0;
	int n, i, p, min = 0, init, maxAngleIndex;
	unsigned int contour[120000], noOfPoints = 0, side = 0;
	freopen("infasuratoare.in", "r", stdin);
	freopen("infasuratoare.out", "w", stdout);
	scanf ("%d", &n);
	for (i=0;i<n;++i)
	{
		scanf("%lf %lf", &points[i][0], &points[i][1]);
		if (points[i][1]<=points[min][1])
			min = i;
	}
		
	init = min;
	p = min;
	contour[noOfPoints++] = p;
	lastAngle = M_PI;
	
	do
	{
		maxAngle = -M_PI;
		for (i = 0;i<n;++i)
		{
			if (i!=p)
			{
				angle = atan2(points[i][1] - points[p][1], points[i][0] - points[p][0]);
				if (side == 0)
				{
					if (angle >= maxAngle)
					{
						maxAngle = angle;
						maxAngleIndex = i;
					}
				}
				else
				{
					if (angle < 0)
						if (angle >= maxAngle)
						{
							maxAngle = angle;
							maxAngleIndex = i;
						}
				}
			}
		}
		
		p = maxAngleIndex;
		if (maxAngle < 0)
			side = 1;
		contour[noOfPoints++] = p;
	}
	while (p != init);

	printf("%u", --noOfPoints);
	for (i = noOfPoints;i>0;--i)
		printf("\n%f %f", points[contour[i]][0], points[contour[i]][1]);

	return 0;
}