Cod sursa(job #1141505)

Utilizator span7aRazvan span7a Data 12 martie 2014 22:08:46
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.82 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
{
    double x,y,tg;
};
punct L[120001];
struct coord{double xx,yy;};
double minx=-M,miny=-M;int n;
int sf;
int sgn(double x){if(x<1)return -1;if(x>1)return 1;return 0;}
vector<coord>sol;
void muta(double &x,double &y)
{
    x=x-sgn(minx)*abs((double)minx);
    y=y-sgn(miny)*abs((double)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].x,L[i].y);
}
double determinant(coord a,coord b,coord c)
{
    double nr=(a.xx-c.xx)*(b.yy-c.yy)-(a.yy-c.yy)*(b.xx-c.xx);
    return sgn(nr);
}
void afisare()
{
    g<<sf<<'\n';
    int i;
    minx=-minx;
    miny=-miny;
    for(i=0;i<sol.size();i++)
        muta(sol[i].xx,sol[i].yy);

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