Cod sursa(job #1509847)

Utilizator Andrei66Andrei Rusu Andrei66 Data 24 octombrie 2015 12:44:31
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <bits/stdc++.h>

// #define x first
// #define y second
#define VM 120005
#define pb push_back
#define ppb pop_back
#define ll long long
#define pdd pair<double, double>
#define eps 1e-12

using namespace std;

//don't forget to put input in the file!!!
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

struct point
{
	double x,y;
}v[VM], st[VM], st2[VM];

int n, vf, vf2;

double crossProduct(point a, point b, point o){
	a.x -= o.x;
	a.y -= o.y;
	b.x -= o.x;
	b.y -= o.y;
	return a.x * b.y - a.y * b.x;
}

bool cmp(point a, point b){
	if(a.x != b.x)	return a.x < b.x;
	return a.y < b.y;
}

int main(){ 
	
	f>>n;
	for(int i=0; i<n; ++i)	f>>v[i].x>>v[i].y;

	sort(v, v + n, cmp);
	// for(int i=0; i<n; ++i)
		// cout<<v[i].x<<' '<<v[i].y<<'\n';

	st[++vf] = v[0];
	st[++vf] = v[1];
	
	for(int i=2; i<n; ++i){
		while(vf >= 2 && crossProduct(st[vf - 1], st[vf], v[i]) < 0)
			--vf;
		st[++vf] = v[i];
	}

	st2[++vf2] = v[n - 1];
	st2[++vf2] = v[n - 2];
	for(int i=n - 3; i>=0; --i){
		while(vf2 >= 2 && crossProduct(st2[vf2 - 1], st2[vf2], v[i]) < 0)
			--vf2;
		st2[++vf2] = v[i];
	}

	g<<vf + vf2 - 2<<'\n';
	for(int i=1; i<=vf; ++i)
		g<<fixed<<setprecision(6)<<st[i].x<<' '<<st[i].y<<'\n';
	for(int i=2; i<vf2; ++i)
		g<<fixed<<setprecision(6)<<st2[i].x<<' '<<st2[i].y<<'\n';

	return 0;
}