Cod sursa(job #1453169)

Utilizator DrumeaVDrumea Vasile DrumeaV Data 22 iunie 2015 19:57:29
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <bits/stdc++.h>
#define x first
#define y second
#define Dim 130000
using namespace std;

typedef pair<double,double> Point;

int N,S[Dim];
Point V[Dim];
bool b[Dim];

void Read()
{
    scanf("%d",&N);

     for (int i = 1;i <= N;i++)
        scanf("%lf%lf",&V[i].x,&V[i].y);
}

inline double Sarrus(Point A,Point B,Point C)
{
    return (B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y);
}

void Convex_Hull()
{
    sort(V + 1,V + N + 1);

     S[1] = 1;
     S[2] = 2;
     int k = 2;
     b[2] = true;

     for (int i = 1,p = 1;i > 0;i += (p = (i == N ? -p : p)))
     {
         if (b[i]) continue;

         while (k > 1 && Sarrus(V[S[k-1]],V[S[k]],V[i]) >=0)
            b[S[k--]] = false;

         S[++k] = i;
         b[i] = true;
     }

     printf("%d\n",--k);

      for (int i = k;i > 0;i--)
        printf("%.6lf %.6lf\n",V[S[i]].x,V[S[i]].y);
}

int main()
{
     freopen("infasuratoare.in","r",stdin);
     freopen("infasuratoare.out","w",stdout);

       Read();
       Convex_Hull();

    return 0;
}