Cod sursa(job #916734)

Utilizator deresurobertoFMI - Deresu Roberto deresuroberto Data 16 martie 2013 20:31:34
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
struct punct{
	float x;
	float y;
}a[120005];
int n,m,i,k;
float x,y,d;
vector<int>v;


int cmp(const punct a,const punct b)
{
	if((a.x-x)*(b.y-y)<=(a.y-y)*(b.x-x))return 0;
                         else return 1;	
}

int re(int x1,int x2,int x3)
{
	d=a[x1].x*a[x2].y+a[x2].x*a[x3].y+a[x3].x*a[x1].y-(a[x1].y*a[x2].x+a[x2].y*a[x3].x+a[x3].y*a[x1].x);
	if(d<0)return 0;
	return 1;
}

int main()
{
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	scanf("%d",&n);
	x=99999999;y=99999999;
	for(i=1;i<=n;i++){
		scanf("%f",&a[i].x);
		scanf("%f",&a[i].y);
		if(y>a[i].y){x=a[i].x;y=a[i].y;k=i;}
		if(y==a[i].y)
			if(x<a[i].x){x=a [i].x;y=a[i].y;k=i;}
	}
	swap(a[1],a[k]);
	sort(a+1,a+n+1,cmp);
	v.push_back(0);
	v.push_back(1);
	v.push_back(2);
	m=2;
	for(i=3;i<=n;i++){
		while(m>=2 && re(v[m-1],v[m],i)==0){
			m--;
			v.pop_back();
		}
		m++;
		v.push_back(i);
	}
	printf("%d\n",m);
	for(i=1;i<=m;i++)printf("%f %f\n",a[v[i]].x,a[v[i]].y);
	return 0;
}