Cod sursa(job #842115)

Utilizator andreea29Iorga Andreea andreea29 Data 26 decembrie 2012 09:11:52
Problema Infasuratoare convexa Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 2.45 kb
//#include<fstream>
#include<algorithm>
#include<cmath>
//#include<iomanip>
#include<cstdio>
  
#define Nmax 120010
#define Num 10000000
  
using namespace std;
  
int n, st[Nmax], viz[Nmax], k;
  
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(fabs(d) < 0.0000000001) 
		return 0;
	if (d > 0)
        return 1;
	else
        return 2;
}
  
void convex ()
{
    st[0] = 0;
    st[1] = 1;
    st[2] = 2;
    viz[1] = viz[2] = 1;
    int 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;
            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 ();
      
  //  h << k << '\n';
    printf ("%d\n", k);
    for (int i = 0; i < k; ++i)
    {
        printf ("%.13lf %.13lf\n", p[st[i]].x, p[st[i]].y);
        //h.precision(6);
        //h << p[st[i]].x << " " << p[st[i]].y << '\n';
    }
  //  h.close();
    return 0;
}