Cod sursa(job #943268)

Utilizator harababurelPuscas Sergiu harababurel Data 24 aprilie 2013 19:41:23
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <cmath>
#define nmax 120005
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);
}

double 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 = 0;
	for(int i=0; i<n; i++) {
		while(top > 2 && cp(v[sol[top-1]], v[sol[top]], v[i]) >= 0.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].x < v[p].x || (v[i].x == v[p].x && v[i].y < v[p].y)) p = i;

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

	hull();

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

	return 0;
}