Cod sursa(job #869458)

Utilizator anaid96Nasue Diana anaid96 Data 1 februarie 2013 17:55:35
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<utility>
using namespace std;

#define y first
#define x second
#define top at(infas.size()-1)
#define prev at(infas.size()-2)
FILE *in,*out;
int n;
vector<pair<double,double> > puncte,infas;
pair<double,double> minim,punct;
bool unghi(pair<double,double> a, pair<double,double> b);
double det(pair<double,double> a,pair<double,double> b,pair<double,double> c);

int main(void)
{
	in=fopen("infasuratoare.in","rt");
	out=fopen("infasuratoare.out","wt");
	fscanf(in,"%d",&n);
	puncte.reserve(n);
	infas.reserve(n);
	fscanf(in,"%lf%lf",&minim.x,&minim.y);
	for(int i=1;i<n;++i)
	{	
		fscanf(in,"%lf%lf",&punct.x,&punct.y);
		if(punct<minim)
		{
			puncte.push_back(minim);
			minim=punct;
		}	
		else
			puncte.push_back(punct);
	}

	sort(puncte.begin(),puncte.end(),unghi);
	vector<pair<double,double> >::iterator it=puncte.begin(),end=puncte.end();
	infas.push_back(minim);
	infas.push_back(*it++);
	
	for(;it!=end;++it)
	{
		while(det(infas.prev,infas.top,*it)<0)
			infas.pop_back();
		infas.push_back(*it);
	}	
	it = infas.begin();    end = infas.end();
		fprintf(out,"%d\n",infas.size());
    for(; it!=end ; ++it)
        fprintf(out,"%lf %lf\n",it->x,it->y);
	
	fclose(in);
	fclose(out);
	return 0;
}

bool unghi(pair<double,double> a, pair<double,double> b)
{	
	return det(minim,a,b)>0;
}	
double det(pair<double,double> a,pair<double,double> b,pair<double,double> c)
{	
	return a.x*b.y + c.x*a.y + b.x*c.y - b.y*c.x -b.x*a.y -c.y*a.x;	
}