Cod sursa(job #1595352)

Utilizator ionut98Bejenariu Ionut Daniel ionut98 Data 10 februarie 2016 11:03:42
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include<fstream>
#include<iomanip>
#include<algorithm>
#define inf 1<<30
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n,k,poz,i,fin[120005];
struct punct
{
    double x,y,panta;
}a[120005],aux,min1;
int cmp(punct nr1,punct nr2)
{
    if(nr1.panta==nr2.panta)
      return nr1.x<nr2.x;
    return nr1.panta<nr2.panta;
}
int conex()
{
    punct nr1,nr2,nr3;
    double arie;
    nr1=a[fin[k-1]];
    nr2=a[fin[k]];
    nr3=a[i];
    arie=(nr1.x*nr2.y+nr2.x*nr3.y+nr1.y*nr3.x-nr3.x*nr2.y-nr3.y*nr1.x-nr1.y*nr2.x)/2;
    if(arie>0)
      return 1;
    return 0;
}
int main()
{
    f>>n;
    min1.x=inf;
    min1.y=inf;
    for(i=1;i<=n;i++)
    {
        f>>a[i].x>>a[i].y;
        if(a[i].x<min1.x||a[i].x==min1.x&&a[i].y<min1.y)
        {
            min1=a[i];
            poz=i;
        }
    }
    aux=a[1];
    a[1]=min1;
    a[poz]=aux;
    for(i=2;i<=n;i++)
      a[i].panta=(a[i].y-a[1].y)/(a[i].x-a[1].x);
    sort(a+2,a+n+1,cmp);
    k=2;
    fin[2]=2;
    fin[1]=1;
    for(i=3;i<=n;i++)
    {
        while(conex()==1&&k>2)
          k--;
        k++;
        fin[k]=i;
    }
    g<<k<<"\n";
    for(i=1;i<=k;i++)
      g<<fixed<<setprecision(6)<<a[fin[i]].x<<" "<<fixed<<setprecision(6)<<a[fin[i]].y<<"\n";
    return 0;
}