Cod sursa(job #708783)

Utilizator halianStefanca Stefan halian Data 7 martie 2012 10:43:52
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 2.23 kb
#include <stdio.h>
#include <math.h>

#define FI fopen("infasuratoare.in","r")
#define FO fopen("infasuratoare.out","w")

struct Punct {
	double x,y;
} punct[120000],stiva[120000];
long n,stivaSize;

void citeste(FILE *f) {
	long i;
	fscanf(f,"%li",&n);
	for(i=0;i<n;i++)
		fscanf(f,"%lf%lf",&punct[i].x,&punct[i].y);
}

void scrie(FILE *f) {
	long i;
	fprintf(f,"%li\n",stivaSize);
	for(i=0;i<stivaSize;i++)
		fprintf(f,"%lf %lf\n",stiva[i].x,stiva[i].y);
}

int compare(Punct a, Punct b) {
	if(a.x<b.x)
		return 1;
	if(a.x>b.x)
		return 0;
	if(a.y<b.y)
		return 1;
	return 0;
}

void schimba(Punct &a, Punct &b) { Punct aux=a;a=b;b=aux; }

void sort(long li,long ls) {
	long i,j;
	if(li>=ls) return;
	for(i=li+1,j=li+1;i<=ls;i++)
		if(compare(punct[i],punct[li]))
			schimba(punct[i],punct[j++]);
	schimba(punct[li],punct[j-1]);
	sort(li,j-2);
	sort(j,ls);
}

void infasuratoare() {
	long i;
	for(i=2;i<n;i++)
		if(stiva[stivaSize-2].x*(stiva[stivaSize-1].y-punct[i].y)+stiva[stivaSize-1].x*(punct[i].y-stiva[stivaSize-2].y)+punct[i].x*(stiva[stivaSize-2].y-stiva[stivaSize-1].y)>=0) {
			stiva[stivaSize]=punct[i];
			stivaSize++;
		}
		else {
			stiva[stivaSize-1]=punct[i];
			while(stivaSize>2 && stiva[stivaSize-3].x*(stiva[stivaSize-2].y-stiva[stivaSize-1].y)+stiva[stivaSize-2].x*(stiva[stivaSize-1].y-stiva[stivaSize-3].y)+stiva[stivaSize-1].x*(stiva[stivaSize-3].y-stiva[stivaSize-2].y)<0) {
				stivaSize--;
				stiva[stivaSize-1]=stiva[stivaSize];
			}
		}
		
	for(i=n-2;i>0;i--)
		if(stiva[stivaSize-2].x*(stiva[stivaSize-1].y-punct[i].y)+stiva[stivaSize-1].x*(punct[i].y-stiva[stivaSize-2].y)+punct[i].x*(stiva[stivaSize-2].y-stiva[stivaSize-1].y)>=0) {
			stiva[stivaSize]=punct[i];
			stivaSize++;
		}
		else {
			stiva[stivaSize-1]=punct[i];
			while(stivaSize>2 && stiva[stivaSize-3].x*(stiva[stivaSize-2].y-stiva[stivaSize-1].y)+stiva[stivaSize-2].x*(stiva[stivaSize-1].y-stiva[stivaSize-3].y)+stiva[stivaSize-1].x*(stiva[stivaSize-3].y-stiva[stivaSize-2].y)<0) {
				stivaSize--;
				stiva[stivaSize-1]=stiva[stivaSize];
			}
		}
}

int main() {
	citeste(FI);
	sort(0,n-1);
	stiva[0]=punct[0];
	stiva[1]=punct[1];
	stivaSize=2;
	infasuratoare();
	scrie(FO);
	return 0;
}