Cod sursa(job #795178)

Utilizator mihaibogdan10Mihai Bogdan mihaibogdan10 Data 7 octombrie 2012 18:36:24
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <cstdio>
#include <algorithm>
#define inf 0xfffffff
using namespace std;

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);
}

int main(){
	freopen("infasuratoare.in", "r", stdin);
	freopen("infasuratoare.out", "w", stdout);
	
	int i;
	scanf("%d", &N);
	for (i = 0; i < N; i++) scanf("%lf %lf",&P[i].x,&P[i].y);

	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];
	}
	
	printf("%d\n", top + 1);
	for (i = 0; i <= top; i++)  printf("%lf %lf\n", st[i].x, st[i].y);
}