Cod sursa(job #840409)

Utilizator andreea29Iorga Andreea andreea29 Data 22 decembrie 2012 16:40:56
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 2.56 kb
//#include<fstream>
#include<algorithm>
#include<cmath>
//#include<iomanip>
#include<cstdio>
#include<iostream>
 
#define Nmax 120010
#define Num 10000000
 
using namespace std;
 
int n, st[Nmax], viz[Nmax], k, s;
 
struct punct 
{
    double x;
    double y;
} p[Nmax];
 
int cmp (punct a, punct b)
{
    if (a.x > b.x || (a.x == b.x && a.y > b.y))
        return 0;
    return 1;
}
 
double dist (punct a, punct b)
{
    return sqrt (double ((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)));
}
 
double det (punct a, punct b, punct c)
{
    return (a.x * b.y + b.x * c.y + c.x * a.y) - (a.y * b.x + b.y * c.x + c.y * a.x);
}
 
int semn (punct a, punct b, punct c)
{
    double d = det (a, b, c);
    if (d > 0)
        return 1;
    else
        if (d < 0)
            return 2;
        else
            return 0;
}
 
void convex ()
{
    st[0] = 0;
    st[1] = 1;
    st[2] = 2;
    viz[1] = viz[2] = 1;
    s = 1; //semn (p[0], p[1], p[2]);
    k = 2;
    int i = 3;
    while (i < n)
    {
        int s1 = semn (p[st[k - 1]], p[st[k]], p[i]);
        while (s != s1 && s1 != 0)
        {
            viz[st[k]] = 0;
            --k;
			if (k == 0)
				cout << i << " ";
            s1 = semn (p[st[k - 1]], p[st[k]], p[i]);
        }
        ++k;
        st[k] = i;
        viz[i] = 1;
        ++i;
    }
    --i;
    while (i >= 0)
    {
        while (viz[i] && i >= 0)
            --i;
		if (i < 0)
			break;
        int s1 = semn (p[st[k - 1]], p[st[k]], p[i]);
        while (s != s1 && s1 != 0)
        {
            --k;
            s1 = semn (p[st[k - 1]], p[st[k]], p[i]);
        }
		++k;
		st[k] = i;
		--i;
    }
}
 
int main()
{
    //ifstream f("infasuratoare.in");
    //ofstream h("infasuratoare.out");
    //f >> n;
	freopen ("infasuratoare.in", "r", stdin);
	freopen ("infasuratoare.out", "w", stdout);
	scanf ("%d", &n);
    for (int i = 0; i < n; ++i)
		scanf ("%lf %lf", &p[i].x, &p[i].y);
      //  f >> p[i].x >> p[i].y;
    //f.close();
    sort (p, p + n, cmp);
	
     
//  for (int i = 0; i < n; ++i)
//      h << p[i].x << " " << p[i].y << '\n';
//  h << '\n'<< '\n';
     
    convex ();
	
	printf ("%d\n", k);
	
	//if (s == 1)
	//{
		for (int i = 0; i < k; ++i)
		{
			printf ("%.6lf %.6lf\n", p[st[i]].x, p[st[i]].y);
        //h.precision(6);
		//h << p[st[i]].x << " " << p[st[i]].y << '\n';
		}
	/*}
	else
	{
		for (int i = k - 1; i >= 0; --i)
			printf ("%.13lf %.13lf\n", p[st[i]].x, p[st[i]].y);

	}*/
  //  h.close();
    return 0;
}