Cod sursa(job #290525)

Utilizator sima_cotizoSima Cotizo sima_cotizo Data 28 martie 2009 00:52:38
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
#include <fstream>
#include <iomanip>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
#define trace(x) cerr<<setprecision(18)<<#x<<"="<<x<<"\n"

#define scanf __tmp=(void*)scanf
#define freopen __tmp=(void*)freopen
void* __tmp;


struct point {
	double x, y;
	point() {}
	point( double a, double b ) { x=a, y=b; }
} ref;
bool operator<(point A, point B) { 
	return A.y<B.y || (A.y==B.y && A.x<B.x);
}

bool test(point A, point B, point C) {
	double dx1 = B.x-A.x, dy1 = B.y-A.y;
	double dx2 = C.x-B.x, dy2 = C.y-B.y;
	return dx1*dy2 > dx2*dy1;
	return atan2(dy1,dx1) > atan2(dy2,dx2);
}
bool comp(point A, point B) {
	double dx1 = A.x-ref.x, dx2 = B.x-ref.x;
	double dy1 = A.y-ref.y, dy2 = B.y-ref.y;
	return dx1*dy2 > dx2*dy1;
}
vector<point> A;

void convex( vector<point> &A ) {
	int N = A.size(), t=0;
	for ( int i=1; i<N; ++i ) 
		t = ( A[i]<A[t] ) ? i : t;
	ref = A[t]; 
	// trace(ref.x); trace(ref.y);
	swap(A[t], A[0]);
	sort(A.begin()+1, A.end(), comp);

	vector<point> r;
	r.push_back(A[0]);
	r.push_back(A[1]);
	for ( int i=2; i<N; ++i ) {
		while ( r.size() >= 2 ) {
			ref = r[r.size()-1];
			if ( test(r[r.size()-2], ref, A[i]) ) break;
			r.pop_back();
		}
		r.push_back(A[i]);
	}
	A = r;
}

int main() {
	freopen("infasuratoare.in", "r", stdin);
	freopen("infasuratoare.out", "w", stdout);
	int N;
	scanf("%d", &N);
	for ( int i=0; i<N; ++i ) {
		double x, y;
		scanf("%lf %lf", &x, &y);
		A.push_back(point(x, y));
	}

	convex(A);

	printf("%d\n", A.size());
	for ( vector<point>::iterator i=A.begin(); i!=A.end(); ++i ) 
		printf("%.6lf %.6lf\n", i->x, i->y);
	return 0;
}