Cod sursa(job #795172)

Utilizator mihaibogdan10Mihai Bogdan mihaibogdan10 Data 7 octombrie 2012 18:24:27
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 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);
}

double SqDist(point A,point B){
	return (A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y);
}

int main(){
	int i;
	fin >> N;
	for (int i = 0; i < N; i++) fin >> 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--;
		
		if (top > 0 && Intoarcere(st[top-1], st[top], P[i]) == 0){
			if (SqDist(st[top-1], st[top]) < SqDist(st[top-1], P[i]))
				st[top] = P[i];
		}
		else st[++top] = P[i];
	}
	
	fout << top + 1 << "\n";
	for (int i = 0; i <= top; i++) fout << st[i].x << " " << st[i].y << "\n";
}