Cod sursa(job #889414)

Utilizator andunhillMacarescu Sebastian andunhill Data 24 februarie 2013 15:01:09
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include<fstream>
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<ctime>
using namespace std;

#define eps 0.000000000001

clock_t start=clock();

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

int N;
pair<double, double>points[120009];

int vf;
int stiva[120009];

bool cmp(pair<double, double>p1, pair<double, double>p2)
{
	return (p1.second - points[1].second) * (p2.first - points[1].first)  - (p2.second - points[1].second) * (p1.first - points[1].first) <=  eps;
}

int semn(int i, int j, int k)
{
	return (points[j].first - points[i].first) * (points[k].second - points[i].second) -
		(points[j].second - points[i].second) * (points[k].first - points[i].first);
}

int main()
{
	int i, j;

	f>>N;
	for(i = 1, j = 1; i <= N; i++)
	{
		f>>points[i].first>>points[i].second;
		if(points[i].second < points[j].second)
			j = i;
		else if(points[i].second == points[j].second && points[i].first < points[j].first)
			j = i;

	}

	swap(points[1], points[j]);
	sort(points + 2, points + N + 1, cmp);

	stiva[1] = 1; stiva[2] = 2; vf = 2;

	for(i = 3; i <= N; i++)
	{
		while(vf >= 2 && semn(stiva[vf - 1], stiva[vf], i) <= 0)
			vf--;
		stiva[++vf] = i;
	}

	g<<vf<<'\n';
	for(i = 1; i <= vf; i++)
		g<<fixed<<setprecision(6)<<points[stiva[i]].first<<" "<<points[stiva[i]].second<<'\n';

    cout << 1.0*(clock()-start)/(1.0*CLOCKS_PER_SEC) << '\n';

    f.close();
    g.close();
    return 0;
}