Cod sursa(job #405652)

Utilizator lorandCsorba Lorand-Alexandru lorand Data 28 februarie 2010 15:12:06
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
using namespace std;
#include<fstream>
#include<algorithm>
struct punct
{
       double x;
       double y;
};
int n, vs=2;
punct v[120005],stiva[120005];
int polare(punct,punct);
int directie(punct,punct,punct);
int main()
{
    int i,poz=0;
    punct aux;
    ifstream fin("infasuratoare.in");
    fin>>n;
    for(i=0;i<n;++i)
       fin>>v[i].x>>v[i].y;
    for(i=1;i<n;++i)
       if(v[i].y<v[poz].y)
         poz=i;
       else
         if(v[i].y==v[poz].y)
           if(v[i].x<v[poz].x)
             poz=i;
    aux=v[0];
    v[0]=v[poz];
    v[poz]=aux;
    sort(v+1,v+n,polare);
    stiva[1]=v[0];
    stiva[2]=v[1];
    for(i=2;i<n;++i)
    {
                    while(directie(stiva[vs-1],stiva[vs],v[i])<=0 && vs>1)
                         --vs;
                    stiva[++vs]=v[i];
    }
    ofstream fout("infasuratoare.out");
    fout<<vs<<'\n';
    for(i=1;i<=vs;++i)
       fout<<fixed<<stiva[i].x<<' '<<stiva[i].y<<'\n';
    return 0;
}
int polare(punct A,punct B)
{
    if(directie(v[0],A,B)>0)
      return 1;
    if(directie(v[0],A,B)<0)
      return 0;
    return(v[0].x-A.x)*(v[0].x-A.x)+(v[0].y-A.y)*(v[0].y-A.y) <
          (v[0].x-B.x)*(v[0].x-B.x)+(v[0].y-B.y)*(v[0].y-B.y);
}
int directie(punct A,punct B,punct C)
{
    double det=A.x*B.y+B.x*C.y+C.x*A.y-C.x*B.y-B.x*A.y-A.x*C.y;
    if(det==0)
      return 0;
    if(det<0)
      return -1;
    return 1;
}