Cod sursa(job #2382779)

Utilizator VadimCCurca Vadim VadimC Data 18 martie 2019 17:56:31
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>

using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

#define NMax 120010
const int inf = (1 << 30);

struct Punct{
	double x, y;
	double tg;
};

int n;
Punct P[NMax];
int s[NMax], vf = -1;

struct CMP{
	bool operator()(Punct & a, Punct & b){
		return a.tg < b.tg;
	}
};

bool arie(Punct &, Punct &, Punct &);

int main(){
	int i, j;
	double x, y;
	int pf = 0;
	fin >> n;
	for(i = 0; i < n; i++){
		fin >> P[i].x >> P[i].y;
		if(P[i].x < P[pf].x || (P[i].x == P[pf].x && P[i].y < P[pf].y)) pf = i;
	}
	swap(P[0], P[pf]);
	P[0].tg = 0;
	P[n] = P[0];
	for(i = 1; i < n; i++){
		if(P[i].x == P[0].x) P[i].tg = inf;
		else P[i].tg = (P[i].y - P[0].y) / (P[i].x - P[0].x);
	}
	sort(P + 1, P + n, CMP());
	s[++vf] = 0;
	s[++vf] = 1;
	for(i = 2; i <= n; i++){
		while(arie(P[s[vf - 1]], P[s[vf]], P[i]) && vf > 1) vf--;
		s[++vf] = i;
	}
	fout << vf << '\n';
	for(i = 0; i < vf; i++)
		fout << P[s[i]].x << ' ' << P[s[i]].y << '\n';
}

bool arie(Punct & a, Punct & b, Punct & c){
	double arie;
	arie = (b.x - a.x)  * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
	return (arie <= 0);
}