Cod sursa(job #1357665)

Utilizator c0rn1Goran Cornel c0rn1 Data 24 februarie 2015 01:18:34
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.73 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <iomanip>
#include <stack>
#include <bitset>
#define NMAX 120008

using namespace std;

int n;
struct point{double x, y;};
point a[NMAX];
stack<int> s;
bitset<NMAX> viz;

void read()
{
   scanf("%d\n", &n);
   for (int i=1; i<=n; ++i)
      scanf("%lf %lf\n", &a[i].x, &a[i].y);
}

bool cmp(point A, point B)
{
   return A.y < B.y || A.y == B.y && A.x > B.x;
}

double panta(point A, point B)
{
   if (B.x == A.x)
      return 0;
   return -(B.y - A.y) / (B.x - A.x);
}

bool cmp2(point A, point B)
{
   double p1 = panta(a[1], A);
   double p2 = panta(a[1], B);
   if (p1 * p2 <= 0)
      return p1 < p2;
   return p1 > p2;
}

double det(point A, point B, point C)
{
   return A.x * B.y + B.x * C.y + A.y * C.x - B.y * C.x - C.y * A.x - A.y * B.x;
}

void write(int x)
{
   if (s.size() == 0)
      return;
   x = s.top();
   s.pop();
   write(x);
   cout<<a[x].x<<" "<<a[x].y<<"\n";
}

void graham()
{
   sort(a+1, a+n+1, cmp);

   double aux[NMAX];
   for (int i=2; i<=n; ++i)
      aux[i] = panta(a[1], a[i]);

   sort(a+2, a+n+1, cmp2);

   for (int i=2; i<=n; ++i)
      aux[i] = panta(a[1], a[i]);

   s.push(1);
   s.push(2);
   int top;
   for (int i = 3; i <= n; ++i){
      top = s.top();
      s.pop();
      while (det(a[s.top()], a[top], a[i]) <= 0){
         top = s.top();
         s.pop();
      }
      s.push(top);
      s.push(i);
   }

   cout<<s.size()<<"\n";
   cout<<fixed<<setprecision(6);
   setprecision(13);
   write(s.top());

}

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

   return 0;
}