Cod sursa(job #768115)

Utilizator igsifvevc avb igsi Data 15 iulie 2012 23:43:44
Problema Infasuratoare convexa Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 3.04 kb
#include<stdio.h>

#define absv(A) ((A) >= 0 ? (A) : -(A))

FILE *in, *out;
double point[120000][2], minX, minY;
int N, heapSize, firstPoint, stack[120000], stSize;

int ifSwap(int i, int j)
{
	/*they have same X coord i.e. slope is infinity*/
	if(point[i][0] == minX && point[j][0] == minX)
	{
		/*i point is higher on Y axis than j point*/
		if(point[i][1] > point[j][1]) return 1;
		else return 0;
	}
	else if(point[i][0] == minX)
	{
		return 1;
	}
	else if(point[j][0] == minX)
	{
		return 0;
	}
	else
	{
		long double slopeI, slopeJ;
		slopeI = ((point[i][1] - minY)/(point[i][0] - minX));
		slopeJ = ((point[j][1] - minY)/(point[j][0] - minX));
		
		//printf("%Lf %Lf %Lf\n", point[i][0], point[i][1], slopeI);
		//printf("%Lf %Lf %Lf\n", point[j][0], point[j][1], slopeJ);
		
		/*if the slope of min with point i is greater than with point j*/
		if(slopeI > slopeJ) return 1;
		/*if the slopes are equal we pick the closest point to min*/
		else if(slopeI == slopeJ && point[i][0] > point[j][0]) return 1;
		else return 0;
		
	}
}

void heapify(int pos)
{
    int next = pos;
    long double aux;
    for(;;)
    {
    	if((pos<<1) <= heapSize && ifSwap(next, (pos<<1)))
    		next <<= 1;
    	if((pos<<1)+1 <= heapSize && ifSwap(next, (pos<<1)+1))
    		next = (pos<<1)+1;
    	if(next == pos) break;
    	aux = point[pos][0]; point[pos][0] = point[next][0]; point[next][0] = aux;
    	aux = point[pos][1]; point[pos][1] = point[next][1]; point[next][1] = aux;
    	pos = next;
    }
}

int popHeap()
{
	long double aux;
	
	aux = point[1][0]; point[1][0] = point[heapSize][0]; point[heapSize][0] = aux;
	aux = point[1][1]; point[1][1] = point[heapSize][1]; point[heapSize][1] = aux;
	heapSize--;
	heapify(1);
	
	return heapSize+1;
}

int main()
{
    int i;
    long double aux;

    in = fopen("infasuratoare.in", "r");
    out = fopen("infasuratoare.out", "w");

	/*reading input data*/
    fscanf(in, "%d", &N);
    for(i = 0; i < N; ++i)
        fscanf(in, "%lf %lf", &point[i][0], &point[i][1]);
    /*done reading data*/
    
    /*finding leftmost point*/
    minX = minY = (1 << 30);
	for(i = 0; i < N; ++i)
		if(point[i][0] < minX || (point[i][0] == minX && point[i][1] < minY))
			minX = point[i][0],
			minY = point[i][1],
			firstPoint = i;
	/*found leftmost point*/	 	
	
	/*creating a minheap*/
	aux = point[0][0]; point[0][0] = point[firstPoint][0]; point[firstPoint][0] = aux;
	aux = point[0][1]; point[0][1] = point[firstPoint][1]; point[firstPoint][1] = aux;
	heapSize = N-1;
	for(i = heapSize>>1; i; --i)
		heapify(i);
	/*done*/
	
	/*finding the convex hull*/
	stack[0] = 0;
	while(heapSize)
	{
		i = popHeap();
		while(stSize && (point[stack[stSize-1]][0]*(point[stack[stSize]][1]-point[i][1]) + 
						 point[stack[stSize]][0]*(point[i][1]-point[stack[stSize-1]][1]) + 
						 point[i][0]*(point[stack[stSize-1]][1]-point[stack[stSize]][1])) < 0)
			stSize--;
		stack[++stSize] = i;
	}
	/*done*/
	
	fprintf(out, "%d\n", stSize+1);
	for(i = 0; i <= stSize; ++i)
		fprintf(out, "%lf %lf\n", point[stack[i]][0], point[stack[i]][1]);
		
    fclose(in);
    fclose(out);
    return 0;
}