Cod sursa(job #624227)

Utilizator mihaibogdan10Mihai Bogdan mihaibogdan10 Data 22 octombrie 2011 00:55:20
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 4.4 kb
#include<cstdio>
#include<vector>
#include<cmath>
#define PI 3.14159265
#define inf 1<<30;

using namespace std;
int N;
double sloap[1000000];

struct point
{
	double x,y;
};
point arrayOfPoints[1000000];

//compute the sloap/gradient (incline) of the line determined by points A and B
double SloapOfLine(point A, point B)
{
	if (B.x == A.x) return -inf;
	return (B.y - A.y)/(B.x - A.x);
}

//HeapSort
void PullDown(int i, int n)
{
	int fiu,done = 0;
	double aux;
	point auxPoint;
	aux = sloap[i]; auxPoint = arrayOfPoints[i];
	
	while (i<=n/2 && !done)
	{
		fiu = 2*i;
		if (fiu + 1 <= n && sloap[fiu+1] > sloap[fiu]) fiu ++;
		
		if (sloap[fiu] > sloap[i])
		{
			sloap[i] = sloap[fiu];
			arrayOfPoints[i] = arrayOfPoints[fiu];
			i = fiu;
		}
		else done = 1;
		sloap[i] = aux;
		arrayOfPoints[i] = auxPoint;
	}
}

void MinHeap()
{
	for (int i = (N-1)/2; i>=1 ;i--) PullDown(i,N-1);
}

void HeapSort()
{
	int i;
	double aux;
	point auxPoint;
	for (i = N-1; i >= 2; i--)
		if (sloap[1] > sloap[i])
		{
			aux  = sloap[1];
			sloap[1] =  sloap[i];
			sloap[i] = aux;
			
			auxPoint = arrayOfPoints[1];
			arrayOfPoints[1] = arrayOfPoints[i];
			arrayOfPoints[i] = auxPoint;
			PullDown(1,i-1);
		}
}


double Angle(point A, point B, point C)
{
	double AB, BC, CA, unghiB;
	
	AB = sqrt((B.x-A.x)*(B.x-A.x) + (B.y-A.y)*(B.y-A.y));
	CA = sqrt((C.x-A.x)*(C.x-A.x) + (C.y-A.y)*(C.y-A.y));
	BC = sqrt((B.x-C.x)*(B.x-C.x) + (B.y-C.y)*(B.y-C.y));
	
	double cosx = (AB*AB + BC*BC - CA*CA)/(2*AB*BC);
	unghiB = acos(cosx) * 180.0 / PI;
	return unghiB;
}
int main()
{
	//read data
	freopen ("infasuratoare.in","r",stdin);
	scanf ("%d", &N);
	int i;
	
	
	//choose a point which is certainly a point of the convex envelope
	//one such point is point witch is the farthest one to the left.
	//should more then one point be situatod on the farthest vertical line, the point with the lowest x will be selected
	scanf("%lf %lf", &arrayOfPoints[0].x, &arrayOfPoints[0].y);
	point tempPt = arrayOfPoints[0];
	int pos = 0; //save the position of the temporary starting point
	for (i=1;i<N;i++)
	{
		scanf("%lf %lf", &arrayOfPoints[i].x, &arrayOfPoints[i].y);
		if (arrayOfPoints[i].x > tempPt.x || (arrayOfPoints[i].x == tempPt.x && arrayOfPoints[i].y < tempPt.y))
			{tempPt = arrayOfPoints[i]; pos = i;}
	}
	//store the starting point at arrayOfPoints[0];
	tempPt = arrayOfPoints[pos];
	arrayOfPoints[pos] = arrayOfPoints[0];
	arrayOfPoints[0] = tempPt;
	fclose(stdin);
	
	//compute the sloap of all line determined by the starting point and any other point
	for (i = 1;i < N;  i++) sloap[i] = SloapOfLine(arrayOfPoints[0],arrayOfPoints[i]);
	
	//sort the points in the array by the sloap of the line each of them determines along with the starting point
	MinHeap();
	HeapSort();
	
	//if two points have the same sloap, delete the one closest to the starting point
	
	for (i=1;i<N-1;i++)
		if (sloap[i]==sloap[i+1])
		{
			for (int j=i;j<N-1;j++)
				{
					arrayOfPoints[j] = arrayOfPoints[j+1];
					sloap[j] = sloap[j+1];
				}
			N--;
		}
	
	//put the first three points on the vector: the starting point and the point highest on the same vertical line
	//if such a point exists, or the starting point and the point at the 1st position in the array
	//arrayOfPoints[2] is the temporary third point
	vector <point> envelope;
	envelope.push_back(arrayOfPoints[0]);
	i=0;
	double maxY = arrayOfPoints[0].y;
	while (arrayOfPoints[i+1].x == arrayOfPoints[0].x)
	{
		if (arrayOfPoints[i+1].y > maxY) maxY = arrayOfPoints[i+1].y;
		i++;
		pos = i;
	}
	if (i!=0) {envelope.push_back(arrayOfPoints[pos]);i++;}
		else {envelope.push_back(arrayOfPoints[1]);i=2;}
	envelope.push_back(arrayOfPoints[2]);
	i++;
	//add the following points 
	//if X Y Z are the last three points and X Y T is a greater angle than X Y Z, then pop Z
	int top;
	for (;i<N;i++)
	{
		top = envelope.size();
		while (top-3 >= 0 && (Angle(envelope[top-3],envelope[top-2],envelope[top-1])< Angle(envelope[top-3],envelope[top-2],arrayOfPoints[i])))
			{envelope.pop_back();top--;}
		envelope.push_back(arrayOfPoints[i]);
	}
	//print the points on the convex envelope
	freopen ("infasuratoare.out","w",stdout);
	//printf("%d \n", N);
	top = envelope.size();
	printf ("%d \n",top);
	for (i=0;i<top;i++)
		printf("%lf , %lf \n", envelope[i].x,envelope[i].y);
	fclose(stdout);
	return 0;
}