Cod sursa(job #1559492)

Utilizator akaprosAna Kapros akapros Data 30 decembrie 2015 22:18:27
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <bits/stdc++.h>
#define maxN 120002
using namespace std;
int n,i,j,p,nr;
struct punct
{
    double x;
    double y;
} q,cp,v[maxN],w[maxN];
double sp(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));
}
double cmp(const punct a,const punct b)
{
    return sp(v[1],a,b)>0;
}
void read()
{
    freopen("infasuratoare.in","r",stdin);
    scanf("%d",&n);
    p=1;
    for (i=1; i<=n; i++)
    {
        scanf("%lf %lf",&v[i].x,&v[i].y);
        if (v[i].x<v[p].x) p=i;
        else if ((v[i].x==v[p].x)&&(v[i].y<v[p].y)) p=i;
    }
}
void solve()
{
     q=v[p];
    punct aux;
    aux=v[p];
    v[p]=v[1];
    v[1]=aux;
    sort(v+2,v+n+1,cmp);
    nr=2;
    w[1]=v[1];
    w[2]=v[2];
    for (i=3; i<=n; i++)
    {
        while ((nr>1)&&(sp(w[nr],w[nr-1],v[i])>0)) nr--;
        w[++nr]=v[i];
    }
}
void write()
{
    freopen("infasuratoare.out","w",stdout);
    printf("%d\n",nr);
    sort(w+1,w+nr+1,cmp);
    for (i=1; i<=nr; i++) printf("%.12lf %.12lf\n",w[i].x,w[i].y);
}
int main()
{
    read();
    solve();
    write();
    return 0;
}