Cod sursa(job #1509823)

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

// #define x first
// #define y second
#define VM 100005
#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;

double crossProduct(int ax, int ay, int bx, int by, int ox, int oy){
	ax -= ox;
	ay -= oy;
	bx -= ox;
	by -= oy;
	return ax * by - ay * bx;
}

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';

	int vf = 0, vf2 = 0;
	st[++vf] = v[0];
	st[++vf] = v[1];
	
	for(int i=2; i<n; ++i){
		while(vf >= 2 && crossProduct(st[vf - 1].x, st[vf - 1].y, st[vf].x, st[vf].y, v[i].x, v[i].y) < 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].x, st2[vf2 - 1].y, st2[vf2].x, st2[vf2].y, v[i].x, v[i].y) < 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;
}