Cod sursa(job #903551)

Utilizator AnteusPatrascoiu Mihai Anteus Data 1 martie 2013 22:10:28
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.61 kb
#include <stdio.h>
#define NMAX 120005
#define INF 1<<30
FILE *f=fopen ("infasuratoare.in", "r");
FILE *g=fopen ("infasuratoare.out", "w");
struct Point2D { double x, y, slope;		//parametrul id folosit pentru a verifica daca in GrahamScan se face corect excluderea nodurilor
				 int id;				}	v[NMAX], aux[NMAX], p;
int st[NMAX];
int n, k;

void read()
{
	p.x = p.y = INF;

	fscanf (f, "%d", &n);

	for (int i = 0; i < n ; i++)
	{
		fscanf (f, "%lf%lf", &v[i].x, &v[i].y);
		v[i].id = i;

		if (p.y > v[i].y)							p = v[i];
		else	if (p.y == v[i].y && p.x > v[i].x)	p = v[i];
	}
}

void calculateSlope(Point2D v[], Point2D p)			//calculeaza panta dreptei dintre V[i] si P
{
	for (int i = 0; i < n; i++)
		if (v[i].id != p.id)
		{
			if (v[i].x != p.x)		v[i].slope = (v[i].y - p.y)/(v[i].x - p.x);
			else					v[i].slope = INF;
		}
}

void Merge(Point2D v[], int lo, int mid, int hi)
{
	for (int i = lo; i <= hi; i++)					//copiaza intr-un vector auxiliar
		aux[i] = v[i];

	int i = lo;
	int j = mid+1;

	for (int k = lo; k <= hi; k++)					//interclasarea
	{
		if (i > mid)								v[k] = aux[j++];
		else	if (j > hi)							v[k] = aux[i++];
		else	if (aux[i].slope < aux[j].slope)	v[k] = aux[i++];
		else										v[k] = aux[j++];
	}
}

void MergeSort(Point2D v[], int lo, int hi)
{
	int mid = lo + (hi-lo)/2;

	if (hi <= lo)	return;

	MergeSort(v, lo, mid);
	MergeSort(v, mid+1, hi);

	Merge(v, lo, mid, hi);
}

void rearrange(Point2D v[])
{
	int j = 0;

	for (int i = 0; i < n && v[i].slope < 0; i++)
		aux[j++] = v[i];
	
	for (int i = 0; i < n; i++)
		if ( i < n - j)		v[i] = v[i+j];
		else				v[i] = aux[i-n+j];
}

bool CounterClockWise(Point2D A, Point2D B, Point2D C)				//	| Ax	Ay	1 |
{																	//	| Bx	By	1 | = (Bx - Ax)(By - Ay) - (By - Ay)(Cx - Ax)
	float val;														//	| Cx	Cy	1 |

	val = (B.x - A.x)*(C.y - A.y) - (B.y - A.y)*(C.x - A.x);		//Counterclockwise rotation if area is > 0

	return val > 0;
}

void GrahamScan(Point2D v[])
{
	st[k++] = 0;
	st[k++] = 1;

	for (int i = 2; i < n; i++)
	{
		while ( !CounterClockWise(v[st[k-2]], v[st[k-1]], v[i]) )
			k--;

		st[k++] = i;
	}
}

int main()
{
	read();

	calculateSlope(v, p);
	MergeSort(v, 0, n-1);
	rearrange(v);

/*	for (int i = 0; i < n; i++)											//tipareste ordinea punctelor sortate dupa unghiul polar
		fprintf (g, "Point %c: %f\n", (char)(65+v[i].id), v[i].slope);	//folosit pentru a verifica daca sortarea se face corect
*/
	GrahamScan(v);

	fprintf (g, "%d\n", k);
	for (int i = 0; i < k; i++)
		fprintf (g, "%lf %lf\n", v[st[i]].x, v[st[i]].y);

	return 0;
}