Cod sursa(job #943262)

Utilizator harababurelPuscas Sergiu harababurel Data 24 aprilie 2013 19:30:24
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <cmath>
#define nmax 120005
//#define x first
//#define y second
using namespace std;

struct point { double x, y; } v[nmax];
int n, i, j, p;
int sol[nmax], top = 0;

int cmp(point a, point b) {
	return (a.y - v[0].y) * (b.x - v[0].x) > (b.y - v[0].y) * (a.x - v[0].x);
}

int cp(point a, point b, point c) {
	return (a.y - b.y) * c.x + (b.x - a.x) * c.y + a.x * b.y - b.x * a.y;
}

void hull() {
	top = -1;
	sol[++top] = 0;
	sol[++top] = 1;
	for(int i=2; i<n; i++) {
		while(top >= 2 && cp(v[sol[top-1]], v[sol[top]], v[i]) >= 0) top--;
		sol[++top] = i;
	}
}
	

int main() {
	ifstream f("infasuratoare.in");
	ofstream g("infasuratoare.out");

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

	p = 0;
	for(i=1; i<n; i++) 
		if(v[i].y < v[p].y || (v[i].y == v[p].y && v[i].x < v[p].x)) p = i;

	swap(v[0], v[p]);
	sort(v+1, v+n, cmp);

	hull();

	g<<fixed;
	g<<top+1<<"\n";
	g<<setprecision(10);
	for(i=top; i>=0; i--) g<<v[sol[i]].x<<" "<<v[sol[i]].y<<"\n";

	return 0;
}