Cod sursa(job #2210164)

Utilizator lucaperjuLuca Perju Verzotti lucaperju Data 5 iunie 2018 19:36:54
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream in ("infasuratoare.in");
ofstream out ("infasuratoare.out");
struct pct
{
	double x,y;
	bool p;
}v[120003];
int st[120003],st1[120003];
bool cmp (pct a, pct b)
{
	if(a.y<b.y)
		return true;
	if(a.y>b.y)
		return false;
	if(a.x<b.x)
		return true;
	return false;
}
bool prt (double x1, double y1, double x2, double y2, double x, double y)
{
	if(x1*y2+x2*y+x*y1<x*y2+x1*y+x2*y1)
		return 1;
	return 0;
}
int main()
{
    int n,i,k=0,s=0,k1;
    double a,b;
    in>>n;
    for(i=1;i<=n;++i)
		in>>v[i].x>>v[i].y;
	sort(v+1,v+n+1,cmp);
	st[++k]=1;
	for(i=2;i<n;++i)
		v[i].p=prt(v[1].x,v[1].y,v[n].x,v[n].y,v[i].x,v[i].y);
	for(i=2;i<=n;++i)
	{
		if(v[i].p==1 || i==n)
		{
            while(k>1 && prt(v[st[k-1]].x,v[st[k-1]].y,v[st[k]].x,v[st[k]].y,v[i].x,v[i].y)==1)
                --k;
            st[++k]=i;
		}
	}
	k1=k;
	s+=k;
    k=0;
    st1[++k]=1;
    for(i=2;i<=n;++i)
	{
		if(v[i].p==0 || i==n)
		{
            while(k>1 && prt(v[st1[k-1]].x,v[st1[k-1]].y,v[st1[k]].x,v[st1[k]].y,v[i].x,v[i].y)==0)
                --k;
            st1[++k]=i;
		}
	}
	s+=k;
    out<<s-2<<'\n';
	for(i=1;i<=k1;++i)
        out<<fixed<<setprecision(12)<<v[st[i]].x<<' '<<v[st[i]].y<<'\n';
	for(i=k-1;i>1;--i)
        out<<fixed<<setprecision(12)<<v[st1[i]].x<<' '<<v[st1[i]].y<<'\n';
    return 0;
}