Cod sursa(job #1912473)

Utilizator raduzxstefanescu radu raduzx Data 8 martie 2017 09:12:12
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
typedef long double ld;
struct punct
{
    ld x,y;
};
#define nmax 120005
punct v[nmax];
int t[nmax];
ld det(punct a,punct b,punct c)
{
    return a.x*b.y+b.x*c.y+a.y*c.x-b.y*c.x-a.y*b.x-a.x*c.y;
}
bool cmp(punct a,punct b)
{
    return (a.y-v[1].y)*(b.x-v[1].x)>(a.x-v[1].x)*(b.y-v[1].y);
}

int main()
{
    int n,k,ind,i;
    f>>n;
    ind=1;
    for(i=1;i<=n;i++)
    {
        f>>v[i].x>>v[i].y;
        if(v[i].x<v[ind].x)
            ind=i;
        else
            if(v[i].x==v[ind].x)
                if(v[i].y<v[ind].y)
                    ind=i;
    }
    swap(v[1],v[ind]);
    sort(v+2,v+n+1,cmp);
    v[0].x=0;
    v[0].y=0;
    t[0]=0;
    t[1]=1;
    k=1;
    ind=2;
   // v[n+1]=v[1];
    while(ind<=n)
    {
        if(det(v[t[k-1]],v[t[k]],v[ind])>0)
        {
            while(k>=2 and det(v[t[k-1]],v[t[k]],v[ind])>0)
                k-=1;
            k+=1;
            t[k]=ind;
        }
        else
        {
            k+=1;
            t[k]=ind;
        }
        ind+=1;
    }
    g<<k<<'\n';
   // g<<fixed<<setprecision(6)<<v[t[1]].x<<" "<<v[t[1]].y<<'\n';
    for(i=k;i>=1;i--)
        g<<fixed<<setprecision(6)<<v[t[i]].x<<" "<<v[t[i]].y<<'\n';
    return 0;
}