Cod sursa(job #934748)

Utilizator vendettaSalajan Razvan vendetta Data 31 martie 2013 12:42:11
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.86 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
#include <iomanip>

using namespace std;

#define x first
#define y second
#define nmax 120005
#define Eps 0.000000000001
#define inf (1<<30)
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

int n, st[nmax];
pair<double, double> v[nmax], Pct;


struct cmp{
   bool operator()(pair<int,int> A, pair<int,int> B){
      // x1 - X / y1 - Y < x2 - X / y2 - Y => (x1 - X) * (y2-Y) < (y1-Y) * (x2-X);
      return( (A.x - Pct.x)*(B.y-Pct.y) < (A.y - Pct.y)*(B.x - Pct.x) );
   }
};

double modul( double x){
   if (x < 0.0) return -x;
   return x;
}

void citeste(){
   f >> n;
   int poz = 0;
   Pct.x = (double)inf;Pct.y = (double)inf;
   for(int i=1; i<=n; ++i){
      f >> v[i].x >> v[i].y;
      if (Pct.x > v[i].x){
         Pct = make_pair(v[i].x, v[i].y); poz = i;
      }else if ( modul( Pct.x - v[i].x) < Eps ){// x-urile sunt egale ma uit la y
         if (Pct.y > v[i].y){
            Pct = make_pair(v[i].x, v[i].y); poz = i;
         }
      }
   }

   swap(v[poz], v[1]);// aduc cel mai din stanga jos punct la inceputul vectorului
   sort(v+2, v+n+1, cmp() );
}


inline double semn(int i , int j , int k){
   return ( v[i].x*v[j].y + v[j].x*v[k].y + v[k].x*v[i].y - v[k].x*v[j].y - v[k].y*v[i].x - v[j].x*v[i].y );
}

void rezolva(){
   st[0] = 2;
   st[1] = 1; st[2] = 2;

   for(int i=3; i<=n; ++i){
      while(st[0] >= 2 && semn(st[ st[0]-1 ], st[ st[0] ], i) >= 0.000000000000){
         --st[0];
      }
      st[ ++st[0] ] = i;
   }

   g << st[0] << "\n";
   g << fixed;
   for(int i=st[0]; i>=1; --i){
      g << setprecision(12) << v[st[i]].x << " " << v[st[i]].y << "\n";
   }
}

int main(){
   setprecision(12);

   citeste();
   rezolva();

   f.close();
   g.close();

   return 0;
}