Cod sursa(job #1338526)

Utilizator bogdanboboc97Bogdan Boboc bogdanboboc97 Data 10 februarie 2015 08:43:36
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <bits/stdc++.h>
#define point pair<double,double>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
point p[120002];
int n,m,st[120002],top;
double det(point x,point y,point z)
{
	return (y.first-x.first)*(z.second-x.second)-(z.first-x.first)*(y.second-x.second);
}
bool comp(point x,point y)
{
	return det(p[1],x,y)>0;
}
int main()
{
	in>>n;
	int mn=1;
	for(int i=1;i<=n;i++)
	{
		in>>p[i].first>>p[i].second;
		if(p[i].second < p[mn].second)mn=i;
		else if(p[i].second==p[mn].second && p[i].first<p[mn].first)mn=i;
	}
	swap(p[1],p[mn]);
	sort(p+2,p+n+1,comp);	
	for(int i=1;i<=n;i++)
    {
        while(top>=2 && det(p[i],p[st[top]],p[st[top-1]]) > 0 )top--;
        st[++top]=i;
    }
	out<<top<<'\n';
    for(int i=1;i<=top;i++)
        out<<fixed<<setprecision(12)<<p[st[i]].first<<" "<<p[st[i]].second<<'\n';
	return 0;
}