Cod sursa(job #1395878)

Utilizator gabib97Gabriel Boroghina gabib97 Data 21 martie 2015 17:47:46
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <stdio.h>
#include <algorithm>
#define inf 1000000000
using namespace std;
int n,i,s[120001],u,j;
double ym,xm;
struct punct
{
    double x,y;
}p[120001];
double det(punct o,punct a,punct b)
{
    return ((a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x));
}
double dist(punct a,punct b)
{
    return ((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool sortare(punct a,punct b)
{
    double r=det(p[1],a,b);
    return (r>0||(r==0&&dist(p[1],a)<dist(p[1],b)));
}
void solve()
{
    int i;
    double r;
    u=2; s[1]=1; s[2]=2;
    for (i=3;i<=n;i++)
    {
        r=det(p[s[u-1]],p[s[u]],p[i]);
        if (r>0) s[++u]=i;
        else if (r==0) s[u]=i;
        else
        {
            while (r<0)
            {
                u--;
                r=det(p[s[u-1]],p[s[u]],p[i]);
            }
            s[++u]=i;
        }
    }
}
int main()
{
    freopen ("infasuratoare.in","r",stdin);
    freopen ("infasuratoare.out","w",stdout);
    scanf("%i",&n);
    ym=xm=inf;
    for (i=1;i<=n;i++)
    {
        scanf("%lf%lf",&p[i].x,&p[i].y);
        if (p[i].y<ym||(p[i].y==ym&&p[i].x<xm))
        {
            ym=p[i].y; xm=p[i].x;
            j=i;
        }
    }
    swap(p[j],p[1]);
    sort(p+2,p+n+1,sortare);
    solve();
    printf("%i\n",u);
    for (i=1;i<=u;i++)
        printf("%f %f\n",p[s[i]].x,p[s[i]].y);
    fclose(stdin);
    fclose(stdout);
    return 0;
}