Cod sursa(job #853047)

Utilizator Luncasu_VictorVictor Luncasu Luncasu_Victor Data 12 ianuarie 2013 01:14:00
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.74 kb
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <cassert>
using namespace std;

#define PRO "infasuratoare"
void OpenFiles(int EVAL)
{
	if(EVAL)
	{
		char input[100] = PRO, output[100] = PRO;
		freopen(strcat(input, ".in"),"r",stdin);
		freopen(strcat(output,".out"),"w",stdout);
	} else
	{
		freopen("test.in","r",stdin);
		freopen("test.out","w",stdout);
	}
}

#define MAX  120001
#define INF 0xffffff
#define EPS 1E-8

int n,nlf,nrt;
struct point{ double x,y; }s[MAX],slf[MAX],srt[MAX];
bool cmp(point a,point b){ return a.x < b.x; }

double delta(point a,point b,point 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;
}

void subsets()
{
	sort(s+1,s+n+1,cmp);
	slf[++nlf]=srt[++nrt]=s[1];
	for(int i=2;i<n;i++)
		if( delta(s[1],s[n],s[i]) > 0 )
			slf[++nlf] = s[i]; else
			srt[++nrt] = s[i];
	slf[++nlf]=srt[++nrt]=s[n];
}

void subsetlf()
{
	int n=2;
	for(int i=3;i<=nlf;i++)
	{
		while(n>=2 && delta(slf[n-1],slf[i],slf[n]) - EPS < 0)n--;
		slf[++n] = slf[i];
	}
	nlf = n;
}

void subsetrt()
{
	int n=2;
	for(int i=3;i<=nrt;i++)
	{
		while(n>=2 && delta(srt[n-1],srt[i],srt[n]) + EPS > 0)n--;
		srt[++n] = srt[i];
	}
	nrt = n;
}

int main(int argv,char *args[])
{
	OpenFiles(argv==0);
	// start
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
			scanf("%lf %lf",&s[i].x,&s[i].y);
		subsets();
		subsetlf();
		subsetrt();
		printf("%d\n",nlf+nrt-2);
		for(int i=nlf;i>0;i--)printf("%lf %lf\n",slf[i].x,slf[i].y);
		for(int i=2;i<nrt;i++)printf("%lf %lf\n",srt[i].x,srt[i].y);
	return 0;
}