Cod sursa(job #1157234)

Utilizator RaduGabriel2012Dinu Radu RaduGabriel2012 Data 28 martie 2014 12:39:59
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cmath>
#define inf 2000000005
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

 struct Punct
 { double x,y; } p[120005];

   double mnx,mny; int n,mnpos,st[120005],k;

 bool eg(double a,double b)
 { return (fabs(a-b)<1e-9); }

 bool comp(Punct a,Punct b)
 { double p1,p2;
     p1=(a.y-mny)/(a.x-mnx);
     p2=(b.y-mny)/(b.x-mnx);

    if (eg(a.x,mnx))
     { p1=inf; if (eg(a.y,mny)) p1=inf+1; }

    if (eg(b.x,mnx))
     { p2=inf; if (eg(b.y,mny)) p2=inf+1; }

   return p1>p2;
 }

 double crossprod(Punct a,Punct b,Punct c)
 {
   return (double) a.x*b.y+b.x*c.y+c.x*a.y-a.y*b.x-b.y*c.x-c.y*a.x;
 }

 void Read()
 {  int i;
   f>>n;
      mny=inf;

    for(i=1;i<=n;i++)
     {f>>p[i].x>>p[i].y;
        if (p[i].x<mnx || (eg(p[i].x,mnx) && p[i].y<mny))
        {mnx=p[i].x; mny=p[i].y; mnpos=i;}
     }
 }

 void Solve()
 { int i;
    k=2; st[1]=1; st[2]=2;

    for(i=3;i<=n;i++)
     { while(k>1 && crossprod(p[st[k-1]],p[st[k]],p[i])>0)
         k--;

        k++; st[k]=i;
     }
 }

int main()
{  int i;

  Read();
  sort(p+1,p+n+1,comp);

  Solve();

     g<<k<<"\n";
   for(i=k;i>=1;i--)
    g<<fixed<<setprecision(6)<<p[st[i]].x<<" "<<p[st[i]].y<<"\n";
    return 0;
}