Cod sursa(job #795167)

Utilizator mihaibogdan10Mihai Bogdan mihaibogdan10 Data 7 octombrie 2012 18:10:51
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <fstream>
#include <algorithm>
#define inf 0xfffffff
using namespace std;
ifstream fin("infasuratoare.in"); ofstream fout("infasuratoare.out");

struct point{
	double x, y;
	bool operator < (point const &b) const{
		return x > b.x || x == b.x && y < b.y;
	}
} P[120001] , st[120001];

int N, top = -1;

double Intoarcere(point &A, point &B, point &C){
	return (A.x * (B.y - C.y) + B.x * (C.y - A.y) + C.x * (A.y - B.y)) / 2;
}

double Sloap(point A, point B){
	if (B.x == A.x) return -inf;
	return (B.y - A.y)/(B.x - A.x);
}

double Cmp (point A, point B){
	return Sloap(P[0], A) < Sloap(P[0], B);
}

void convex(){
	int i;
	sort(P, P + N);
	sort(P + 1, P + N, Cmp);
	
	for (i = 0; i < N; i++){
		while (top > 1 && Intoarcere(st[top-1], st[top], P[i]) <= 0) top--;
		st[++top] = P[i];
	}
}

int main(){
	fin >> N;
	for (int i = 0; i < N; i++) fin >> P[i].x >> P[i].y;

	convex();
	
	fout << top + 1 << "\n";
	for (int i = 0; i <= top; i++) fout << st[i].x << " " << st[i].y << "\n";
}