Cod sursa(job #477196)

Utilizator robigiirimias robert robigi Data 13 august 2010 19:34:27
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.02 kb
// Infasuratoare convexa.cpp : Defines the entry point for the console application.
//

//#include "stdafx.h"
#include "stdio.h"
#include <algorithm>
#include "math.h"

using namespace std;


FILE *f=fopen("infasuratoare.in", "r");
FILE *g=fopen("infasuratoare.out", "w");


struct pct
{
	double x, y;
};

int n;
pct v[120001];
int ind[120001];
int st[120001];
int pctin, pi;


bool cmpf(int i,int j) 
{     
	return (double)(v[i].x - v[pctin].x) * (v[j].y - v[pctin].y) < (double)(v[j].x - v[pctin].x) * (v[i].y - v[pctin].y); 
} 




int comp(pct x, pct y)
{
	if ( (x.x-v[pctin].x)*(y.y-v[pctin].y)<(y.x-v[pctin].x)*(x.y-v[pctin].y))
		return 1;
	return 0;
}

int semn(int i1, int im, int i2)
{
	if ( v[i1].x*v[im].y+v[im].x*v[i2].y+v[i2].x*v[i1].y-v[i1].y*v[im].x-v[im].y*v[i2].x-v[i2].y*v[i1].x<0) return 0;
	return 1;
}


void quicksort(int lo, int hi)
{
	double h;
	pct x=v[(lo+hi)/2];
	int i=lo, j=hi;
	do
	{
		while (comp(v[i], x)==1 && i<hi) i++;
		while (comp(v[j], x)==0 && j>lo) j--;
		if (i<=j)
		{
			h=v[i].x; v[i].x=v[j].x; v[j].x=h;
			h=v[i].y; v[i].y=v[j].y; v[j].y=h;
			i++; j--;
		}
	}
	while (i<=j);
	if (j>lo) quicksort(lo, j);
	if (i<hi) quicksort(i, hi);
}



void read()
{
	v[0].x=100000000000.00000;
	fscanf(f, "%d", &n);
	for (int i=1; i<=n; ++i)
	{
		fscanf(f, "%lf%lf", &v[i].x, &v[i].y);
		if (v[i].x<v[pctin].x || v[i].x==v[pctin].x && v[i].y<v[pctin].y)
			pctin=i;
	}
}



int main()
{
	read();
		
	int pi=pctin;
	pct aux=v[pi];
	for (int i=1; i<=n; ++i)
	{
		if (i==pi) continue;
		ind[++ind[0]]=i;
	}

//	quicksort(1, n);
	sort(ind + 1,ind + ind[0] + 1,cmpf); 

	st[++st[0]]=pi;

	for (int j=1; j<=ind[0]; ++j)
	{
		if (ind[j]==pi) continue;
		while (st[0]>=2 && semn(st[st[0]-1], st[st[0]], ind[j])==1 ) 
			--st[0];
		st[++st[0]]=ind[j];
	}

	fprintf (g, "%d\n", st[0]);
	fprintf(g, "%lf %lf\n", aux.x, aux.y);
	for (int k=st[0]; k>1; --k)
		fprintf(g, "%lf %lf\n", v[st[k]].x, v[st[k]].y);

	
	return 0;
}