Cod sursa(job #2383529)

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

using namespace std;

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

struct punct
{
	double x, y;
}st[120001], v[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;
	}
}

/*bool cmp2(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;
	}
}*/

/*void parcurg()
{
    sort(st+1, st+n+1, cmp);
	int c = 2;
	v[1] = st[1];
	while(c != n)
	{
		if(det(st[1], st[n], st[c])<0)
		{
			v[++nr] = st[c];
			if(c>2 && det(st[c-2], st[c-1], st[c])<0)
			{
				v[nr-1] = v[nr];
				--nr;
			}
		}
        c++;
	}

	while(c != 1)
	{
		if(det(st[1], st[n], st[c])>0)
		{
			v[++nr] = st[c];
			if(c<n-1 && det(st[c+2], st[c+1], st[c])<0)
			{
				v[nr-1] = v[nr];
				--nr;
			}
		}
        c--;
	}

}*/

int main()
{
    int n, nr = 1, k = 0;
    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;
	v[1] = st[1];
	while(c != n)
	{
		if(det(st[1], st[n], st[c])<0)
		{
			v[++nr] = st[c];
			if(nr>2 && det(v[nr-2], v[nr-1], v[nr])<0)
			{
				v[nr-1] = v[nr];
				--nr;
			}
		}
        c++;
	}
    v[++nr] = st[n];
	while(c != 1)
	{
		if(det(st[1], st[n], st[c])>0)
		{
			v[++nr] = st[c];
			++k;
			if(k>2 && det(v[nr-2], v[nr-1], v[nr])<0)
			{
				v[nr-1] = v[nr];
				--nr;
			}
		}
        c--;
	}
    out<<nr<<endl;
    for(int i = 1; i<=nr; i++)
        out<<setiosflags(ios::showpoint)<<v[i].x<<" "<<v[i].y<<'\n';


    return 0;
}