Cod sursa(job #1142615)

Utilizator span7aRazvan span7a Data 13 martie 2014 23:24:27
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.89 kb
#include<fstream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<iomanip>
#define M -2000000000
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct punct
{
   long double x,y,tg;
};
punct L[120001];
struct coord{long double xx,yy;};
long double minx=-M,miny=-M;int n;
int sf;
vector<coord>sol;
void muta(long double &x,long double &y)
{
    x=x-minx;
    y=y-miny;
}
int cmp(punct a,punct b)
{
    return a.tg<b.tg;
}
void citire()
{
    int i;
    f>>n;
   for(i=1;i<=n;i++)
   {
       f>>L[i].x>>L[i].y;
       if(minx>L[i].x)
       {
            minx=L[i].x;
            miny=L[i].y;
        }
       else
            if(minx==L[i].x)
                if(miny>L[i].y)
                    miny=L[i].y;
   }
   for(i=1;i<=n;i++) muta(L[i].x,L[i].y);
   for(i=1;i<=n;i++) L[i].tg=atan2(L[i].y,L[i].x);
}
long double determinant(coord a,coord b,coord c)
{
   long double nr=(a.xx-c.xx)*(b.yy-c.yy)-(a.yy-c.yy)*(b.xx-c.xx);
    return nr;
}
void afisare()
{
    g<<sf<<'\n';
    int i;
    minx=-minx;
    miny=-miny;
    for(i=0;i<sf;i++)
        muta(sol[i].xx,sol[i].yy);

    for(i=sf-1;i>=0;i--)
        g<<fixed<<setprecision(12)<<sol[i].xx<<" "<<sol[i].yy<<'\n';
}
void infasuratoare()
{
    int i;
    coord c;
    c.xx=0;c.yy=0;sol.push_back(c);
     c.xx=L[1].x;c.yy=L[1].y;sol.push_back(c);
     // c.xx=L[2].x;c.yy=L[2].y;sol.push_back(c);
    sf=2;
    for(i=2;i<=n;i++)
    {
        c.xx=L[i].x;c.yy=L[i].y;
        while(sol.size()>=2&&determinant(sol[sf-2],c,sol[sf-1])>0)
        {
            sol.pop_back();
            sf--;
        }
        sol.push_back(c);sf++;
    }
}
int main()
{   int i;
    citire();
    sort(L+1,L+n+1,cmp);
    infasuratoare();
    afisare();
   /* for(i=1;i<=n;i++)
        g<<L[i].x<<" "<<L[i].y<<" "<<L[i].tg<<'\n';*/
    return 0;
}