Cod sursa(job #3247471)

Utilizator Andrei_Gagea08Andrei Gagea Andrei_Gagea08 Data 7 octombrie 2024 21:16:58
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 kb
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");

struct vect
{
	double x,y;
	int p = -2;
}v[120001];
int st[120001],vf=0;


bool cmp(vect a,vect b)
{
	if (a.x < b.x)
		return 1;
	else if (a.x == b.x && a.y < b.y)
		return 1;
	else
		return 0;
}
double functie(vect a, vect b, vect c)
{
	return a.x * b.y + b.x * c.y + c.x * a.y - a.y * b.x - b.y * c.x - c.y * a.x;
}

int main()
{
    int i,n;
	cin>>n;

	for(i=1;i<=n;i++)
		cin>>v[i].x>>v[i].y;

	sort(v+1,v+n+1,cmp);

	v[1].p=0;
	v[n].p=0;
	for(i=2;i<n;i++)
	{
		double a=functie(v[1],v[n],v[i]);
		if(a<0)
			v[i].p=-1;
		else if(a>0)
			v[i].p=1;
		else if(a==0)
			v[i].p=0;
	}

	for(i=1;i<=n;i++)
		if(v[i].p<=0)
        {
            if(vf<2)
                st[++vf]=i;
            else
            {
                while(vf>=2 && functie(v[st[vf-1]],v[st[vf]],v[i])<0)
                    vf--;
                st[++vf]=i;
            }
        }

	int dx=vf;
	for(i=n-1;i>0;i--)
		if(v[i].p>=0)
		{
		    if(vf<dx+1)
                st[++vf]=i;
            else
            {
                while(vf>=dx+1 && functie(v[st[vf-1]],v[st[vf]],v[i])<0)
                    vf--;
                st[++vf]=i;
            }
		}


	cout<<vf-1<<'\n'<<fixed<<setprecision(6);

	for(i=2;i<=vf;i++)
		cout<<v[st[i]].x<<' '<<v[st[i]].y<<'\n';
	return 0;
}