Cod sursa(job #1128794)

Utilizator AndreilAndrei Lecu Andreil Data 27 februarie 2014 18:45:35
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <stdio.h>
#include<algorithm>
using namespace std;
struct Punct{double x,y;};
Punct p[120005],s[120005];
int n,varf;
void cit()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    int i;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    scanf("%lf%lf",&p[i].x,&p[i].y);
}
inline double produs(const Punct& A,const Punct& B,const Punct& C)
{
    return (B.x-A.x)*(C.y-A.y) - (B.y-A.y)*(C.x-A.x);
}
inline int cmp(const Punct& p1, const Punct& p2)
{
    return produs(p[1],p1,p2)<0;
}
void swap(int i, int j)
{
    Punct aux;
    aux=p[i];
    p[i]=p[j];
    p[j]=aux;
}
void sortp()
{
    int i,k=1;
    for(i=2;i<=n;i++)
    if(p[k].x>p[i].x)
    k=i;
    else
    if(p[k].x==p[i].x)
    if(p[k].y>p[i].y)
    k=i;
    swap(1,k);
    sort(p+2,p+n+1,cmp);
}
void infasuratoare()
{
    sortp();
    s[1]=p[1];
    s[2]=p[2];
    varf=2;
    for(int i=3;i<=n;i++)
    {
        while(varf>1 && produs(s[varf-1],s[varf],p[i])>0)
        --varf;
        s[++varf]=p[i];
    }
}
void afis()
{
    printf("%d\n",varf);
    for(int i=varf;i>=1;i--)
    printf("%.9lf %.9lf\n",s[i].x,s[i].y);
}
int main()
{
    cit();
    infasuratoare();
    afis();
    return 0;
}