Cod sursa(job #1650432)

Utilizator RadduFMI Dinu Radu Raddu Data 11 martie 2016 18:17:49
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
double inf=1000000003;

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

int n,k;
double px=inf,py;

double cross(pct a,pct b,pct 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;
}

double panta(pct a)
{ return (double) (a.y-py)/(a.x-px); }

bool comp(pct a,pct b)
{ double e1=(double) (a.y-py)/(a.x-px), e2=(double) (b.y-py)/(b.x-px);
  if (a.y==py && a.x==px) return 1;
  if (b.y==py && b.x==px) return 0;
  return e1>e2;
}

int main()
{ int i,j;
    f>>n;

    for(i=1;i<=n;i++)
     {f>>p[i].x>>p[i].y;
      if (p[i].x<px || (p[i].x==px && p[i].y<py))
       {px=p[i].x; py=p[i].y;}
     }


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



    k=3; a[1]=p[1]; a[2]=p[2]; a[3]=p[3];

    for(i=4;i<=n;i++)
    { //cout<<p[i].x<<" "<<p[i].y<<"\n";

    if (i==4)
     {
       //cout<<cross(a[2],a[3],p[i]);
     }

      while(k>=3 && cross(a[k-1],a[k],p[i])>=0)
       k--;

      k++; a[k]=p[i];



    }
    g<<k<<"\n";

    for(i=1;i<=k;i++)
     g<<fixed<<setprecision(12)<<a[i].x<<" "<<a[i].y<<"\n";

    return 0;
}