Cod sursa(job #629438)

Utilizator dany123Florea Daniel dany123 Data 3 noiembrie 2011 12:51:55
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.84 kb
#include<iostream>
#include<fstream>
#include<iomanip>
using namespace std;
int n,k_st,k_v;
struct pct{double x,y;};
pct v[120001],st[120001],pr,man;
void citire()
{
	ifstream fin("infasuratoare.in");
	fin>>n;
	
	fin>>v[1].x>>v[1].y;
	pr=v[1];
	
	int i2;//poz primului
	for (int i=2;i<=n;i++) //pr va fi cel mai din stanga, apoi jos
	{
		fin>>v[i].x>>v[i].y;
		if (v[i].x<pr.x) {pr=v[i]; i2=i;}
		if (v[i].x==pr.x && v[i].y<pr.y) {pr=v[i]; i2=i;}
	} 
	man=v[1]; v[1]=pr; v[i2]=man;
	fin.close();
}
inline double panta (pct a) {return ((a.y-pr.y)/(a.x-pr.x));}
inline int mai_mic (pct a, pct b) {if (panta(a)<panta(b)) return 1; return 0;}
void mergesort(int i, int mij, int j)
{
	pct v2[120001];
	int i1=i,i2=mij+1;
	int k=0;
	while (i1<=mij && i2<=j)
	{
		if (mai_mic(v[i1],v[i2])==1)
			v2[k++]=v[i1++];
		else 
			v2[k++]=v[i2++];
	}
	while (i1<=mij) v2[k++]=v[i1++];
	while (i2<=j) v2[k++]=v[i2++];
	
	int cop=i;
	for (int d=0;d<=(j-i);d++)
		v[cop++]=v2[d];
}

void sortare(int i, int j)
{
	if (i<j)
	{
		int mij=(i+j)/2;
		sortare(i,mij);
		sortare(mij+1,j);
		mergesort(i,mij,j);
	}
}
inline double determinant(pct a, pct b, pct c)
{return (a.x*b.y + a.y*c.x + c.y*b.x - b.y*c.x - c.y*a.x - b.x*a.y);}
void margine(pct a, pct b, pct c)
{
	
	if (determinant(a,b,c)<0)
	{
		k_st--;
		margine(st[k_st-1],st[k_st],v[k_v]);
	}
	else
	{
		st[++k_st]=v[k_v++];
		if (k_v==n+1) return;
		margine(st[k_st-1],st[k_st],v[k_v]);
	}
}
int main ()
{
	citire();
	sortare(2,n);
	st[1]=v[1];//primul
	st[2]=v[2];//al 2-lea
	k_st=2;
	k_v=3;
	margine(st[k_st-1],st[k_st],v[k_v]);
	
	ofstream fout("infasuratoare.out");
	fout.setf(ios::floatfield);            
	fout.precision(12);
	fout<<fixed;
	fout<<k_st<<'\n';
	for (int i=1;i<=k_st;i++)
		fout<<st[i].x<<' '<<st[i].y<<'\n';
	fout.close();
	return 0;
}