Cod sursa(job #846833)

Utilizator test_13testing test_13 Data 2 ianuarie 2013 20:47:13
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <set>
using namespace std;
#define inf 0xffffff
#define Max 120001
#define eps 1e-6

struct point { double x,y; }s[Max],st[Max],dr[Max];
int n,nst,ndr;
bool sort_type(point a,point b){ return a.x<b.x; }

double delta(point a,point b,point c)
{/*
 1 a.x a.y
 1 b.x b.y
 1 c.x c.y
 1 a.x a.y
 1 b.x b.y*/
	return b.x*c.y + c.x*a.y + a.x*b.y - a.y*b.x - b.y*c.x - c.y*a.x;
}

void st_envelope()
{
	int n=2;
	for(int i=3;i<=nst;i++)
	{
		while(n>=2 && delta(st[n-1],st[i],st[n]) + eps < 0)n--;
		st[++n]=st[i];
	}
	nst=n;
}

void dr_envelope()
{
	int n=2;
	for(int i=3;i<=ndr;i++)
	{
		while(n>=2 && delta(dr[n-1],dr[i],dr[n]) - eps > 0)n--;
		dr[++n]=dr[i];
	}
	ndr=n;
}

void envelope()
{
	sort(s+1,s+n+1,sort_type);
	//for(int i=1;i<=n;i++)printf("%lf %lf\n",s[i].x,s[i].y);
	point p = s[1], u = s[n];
	st[++nst]=dr[++ndr]=p;
	for(int i=2;i<n;i++)
		if(delta(p,u,s[i])-eps>0) st[++nst]=s[i]; else dr[++ndr]=s[i];
	st[++nst]=dr[++ndr]=u;

	st_envelope();
	dr_envelope();

	//for(int i=1;i<=ndr;i++)printf("%lf %lf\n",dr[i].x,dr[i].y);
	printf("%d\n",nst+ndr-2);
	for(int i=nst;i>0;i--)printf("%lf %lf\n",st[i].x,st[i].y);
	for(int i=2;i<ndr;i++)printf("%lf %lf\n",dr[i].x,dr[i].y);
}

int main()
{
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
		scanf("%d",&n);
		for(int i=1;i<=n;i++) scanf("%lf %lf",&s[i].x,&s[i].y);
		envelope();
	return 0;
}