Cod sursa(job #1266764)

Utilizator pitradaPit-Rada Ionel-Vasile pitrada Data 19 noiembrie 2014 01:40:30
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.66 kb
#include<fstream>
#include<cstdlib>
using namespace std;

ifstream  fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

struct punct
{
    double x,y;
};

int compare (const void * a, const void * b)
{
  if ( (*(punct*)a).x <  (*(punct*)b).x ) return -1;
  if ( (*(punct*)a).x == (*(punct*)b).x && (*(punct*)a).y <  (*(punct*)b).y ) return -1;
  if ( (*(punct*)a).x >  (*(punct*)b).x ) return +1;
  if ( (*(punct*)a).x == (*(punct*)b).x && (*(punct*)a).y >  (*(punct*)b).y ) return +1;
  return 0;
}

int unghi(punct A, punct B, punct C)
{
    double p,q;
    p=A.x*B.y+B.x*C.y+C.x*A.y;
    q=C.x*B.y+A.x*C.y+B.x*A.y;
    if(p<q)return -1;
    if(p>q)return +1;
    return 0;
}

int N, nup, ndown, i;
punct V[120005],Up[120005], Down[120005];

int main()
{
    fin>>N;
    for(i=1;i<=N;i++)
    {
        fin>>V[i].x>>V[i].y;
    }
    qsort(V+1,N,sizeof(punct),compare);
    Up[1]=V[1];
    nup=1;
    for(i=2;i<=N-1;i++)
    {
        if(unghi(V[1],V[i],V[N])<=0)
        {
            while(nup>=2 && unghi(Up[nup-1],Up[nup],V[i])>0)
            {
                nup--;
            }
            nup++;
            Up[nup]=V[i];
        }
    }
    Down[1]=V[1];
    ndown=1;
    for(i=2;i<=N;i++)
    {
        if(unghi(V[1],V[i],V[N])>=0)
        {
            while(ndown>=2 && unghi(Down[ndown-1],Down[ndown],V[i])>0)
            {
                ndown--;
            }
            ndown++;
            Down[ndown]=V[i];
        }
    }
    fout<<ndown+nup-1<<'\n';
    for(i=1;i<=ndown;i++)
    {
        fout<<Down[i].x<<" "<<Down[i].y<<'\n';
    }
    for(i=nup;i>=2;i--)
    {
        fout<<Up[i].x<<" "<<Up[i].y<<'\n';
    }
    fout.close();
    fin.close();
    return 0;
}