Cod sursa(job #2383623)

Utilizator vladuteluVlad Oancea vladutelu Data 19 martie 2019 18:13:54
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <bits/stdc++.h>

using namespace std;

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

struct punct
{
	double x, y;
}st[120001], vs[120001], vd[120001];

int det(punct a, punct b, punct c)
{
	return a.x * b.y + b.x * c.y + c.x * a.y - c.x * b.y - a.x * c.y - b.x * a.y;
}

bool cmp(punct a, punct b)
{
	if(a.y<b.y)
		return true;
	else if(a.y>b.y)
		return false;
	else
	{
		if(a.x<b.x)
			return true;
		return false;
	}
}

int main()
{
    int n, nrs = 1, nrd = 1;
    in>>n;
    for(int i = 1; i<=n; i++)
	{
		in>>st[i].x>>st[i].y;
	}
    sort(st+1, st+n+1, cmp);
	int c = 2;
	vs[1] = st[1];
	vd[1] = st[1];
	while(c != n)
	{
		if(det(st[1], st[n], st[c])<0)
		{
		    while(nrd>2 && det(vs[nrd-1], vs[nrd], st[c])<0)
                --nrd;
			vd[++nrd] = st[c];
		}
		else
        {
            while(nrs>2 && det(vs[nrs-1], vs[nrs], st[c])>0)
                --nrs;
			vs[++nrs] = st[c];
        }
        c++;
	}
    vd[++nrd] = st[n];
    out<<nrs+nrd-1<<'\n';
    for(int i = 1; i<=nrd; i++)
        out<<fixed<<setprecision(6)<<vd[i].x<<" "<<vd[i].y<<'\n';

    for(int i = nrs; i>=2; i--)
        out<<fixed<<setprecision(6)<<vs[i].x<<" "<<vs[i].y<<'\n';

    return 0;
}