Cod sursa(job #544898)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 2 martie 2011 13:05:51
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include <stdio.h>
#include <algorithm>
using namespace std;
#define DIM 120005

int N, O, S[DIM];
struct punct { double x, y; } P[DIM], T;

int cmp (punct a, punct b)
{
	return a.y * b.x < a.x * b.y;
}

int determ3 (int a, int b, int c)
{
	double X1, X2, X3, Y1, Y2, Y3;
	X1 = P[a].x, Y1 = P[a].y;
	X2 = P[b].x, Y2 = P[b].y;
	X3 = P[c].x, Y3 = P[c].y;	
	return (X3 - X2) * (Y1 - Y2) - (X1 - X2) * (Y3 - Y2) < 0;	
}
/*
int convex(int P1, int P2, int P3) {
    long double A, X1, Y1, X2, Y2, X3, Y3;
     
    X1 = P[P1].x, Y1 = P[P1].y, X2 = P[P2].x, Y2 = P[P2].y, X3 = P[P3].x, Y3 = P[P3].y;
    A = (X3 - X2) * (Y1 - Y2) - (X1 - X2) * (Y3 - Y2);
     
    if (A > 0)
        return 1;
    return 0;
}
*/
void citire ()
{
	scanf ("%d", &N);
	for (int i = 0; i < N; i++)
	{
		scanf ("%lf%lf", &P[i].x, &P[i].y);
		if (P[O].y > P[i].y)
			O = i;
	}
}

void sortare ()
{
	punct aux = P[O]; P[O] = P[0]; P[0] = aux;
	T = P[0];
	for (int i = 0; i < N; i++)
		P[i].x -= T.x, P[i].y -= T.y;
	sort (P + 1, P + N, cmp);
}
	
void infasoara ()
{
	S[++S[0]] = 0;
	S[++S[0]] = 1;
	
	for (int i = 2; i < N; i++)
	{
		while (S[0] > 2 && /*!convex(S[S[0]-1], S[S[0]], i)*/ determ3 (S[S[0] - 1], S[S[0]], i))
			S[0] --;
		S[++S[0]] = i;
		
	}
}

void afisare ()
{
	printf ("%d\n", S[0]);
	for (int i = 1; i <= S[0]; i++)
		printf ("%lf %lf\n", P[S[i]].x + T.x, P[S[i]].y + T.y);
}

int main ()
{
	freopen ("infasuratoare.in", "r", stdin);
	freopen ("infasuratoare.out", "w", stdout);
	
	citire ();
	sortare ();
	infasoara ();
	afisare ();
	
	return 0;
}