Cod sursa(job #832259)

Utilizator johnny2008Diaconu Ion johnny2008 Data 10 decembrie 2012 10:15:00
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include<fstream>
#include<iostream>
#include <algorithm>
using namespace std;
struct Punct{double x,y;};
Punct stack[120001];
int k;
bool cmp(Punct a,Punct b){
    if(a.y<b.y)
        return true;
    if(a.y==b.y && a.x<b.x)
        return true;
    return false;
}
int semn(Punct a , Punct b, Punct c)
{
	if((b.x * c.y + a.x * b.y + c.x  * a.y- a.y * b.x - c.x * b.y - a.x * c.y) >=0) return 1;
	else  return 0;
}
void infas(Punct a[120001],int n){
	int i;
	
	sort(a+1 , a + n + 1, cmp);
	
	stack[1]=a[1];
	k = 1;
	for(i = 2; i <= n; i++)
	{
		while(k > 1 && !semn(stack[k-1], stack[k], a[i])) k--;
		stack[++k]=a[i];
	}
	for(i = n - 1; i >= 1; i--)
	{
		while(!semn(stack[k-1], stack[k], a[i]))k--;
		stack[++k]=a[i];
	}
}
int main()
{
	ifstream f("infasuratoare.in");
	ofstream g("infasuratoare.out");

	Punct a[120001];
	int n;
	f>>n;
	
	int i;
	for(i=1;i<=n;i++){
		f>>a[i].x>>a[i].y;
	}
	infas(a,n);
	g<<k-1<<"\n";
	for(i=1;i<k;i++){
		g<<stack[i].x<<" "<<stack[i].y<<"\n";
	}
	
	
	return 0;

}