Cod sursa(job #1129784)

Utilizator Dddarius95Darius-Florentin Neatu Dddarius95 Data 28 februarie 2014 09:21:39
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include<fstream>
#include<cmath>
#include<algorithm>
using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

int N,k;

struct point { double x,y;} P[120090],st[120009];

double crossproduct(point A,point B,point C)
{
     return static_cast<double>(A.x*B.y+A.y*C.x+B.x*C.y-B.y*C.x-A.y*B.x-A.x*C.y);
}

bool cmp(point A,point B)
{
     return crossproduct(P[1],A,B)>0;
}

int main()
{
     f>>N;
     f>>P[1].x>>P[1].y;
     for(int i=2;i<=N;++i)
     {
          f>>P[i].x>>P[i].y;
          if(P[1].x>P[i].x || (P[1].x==P[i].x && P[1].y>P[i].y))
               swap(P[1],P[i]);
     }
     sort(P+2,P+1+N,cmp);
     st[1]=P[1], st[2]=P[2];
     k=2;
     for(int i=3;i<=N;++i)
     {
          while(crossproduct(st[k-1],st[k],P[i])<0 && k>=2)--k;
          st[++k]=P[i];
     }
     g<<k<<'\n';
     g.precision(12);
     for(int i=1;i<=k;++i)
          g<<fixed<<st[i].x<<' '<<st[i].y<<'\n';

     f.close();g.close();
     return 0;
}