Cod sursa(job #1014758)

Utilizator Barcau_EmanuelBarcau Emanuel Barcau_Emanuel Data 23 octombrie 2013 11:06:50
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include<stdio.h>
#include<algorithm>
#define Nmax 120010
#define INF 1<<30
using namespace std;

int i,n,k,s[Nmax],poz;

struct punct
{
    double x,y,panta;
} v[Nmax],o,aux;

int cmp ( punct a, punct b)
{
    if(a.panta==b.panta) return a.x<b.x;

    return a.panta<b.panta;
}

int convex()
{
    punct a,b,c;
    double S;

    a=v[s[k-1]];
    b=v[s[k]];
    c=v[i];

    S = ( a.x-c.x ) * ( b.y-a.y ) + ( a.x-b.x ) * ( a.y-c.y ) ;

    if(S>0) return 1;
    return 0;
}


int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);

    scanf("%d",&n);

    o.x=o.y=INF;

    for(i=1;i<=n;i++)
    {
        scanf("%lf %lf",&v[i].x,&v[i].y);

        if(v[i].x < o.x || v[i].x == o.x && v[i].y < o.y)
            o=v[i],poz=i;
    }

    aux=v[1]; v[1]=v[poz]; v[poz]=aux;

    for(i=2;i<=n;i++)
        v[i].panta = ( v[i].y - o.y ) / (v[i].x - o.x);
      for(i=2;i<=n;i++)
        printf("%lf\n",v[i].panta);

    sort(v+2,v+n+1,cmp);

    s[1]=1; s[2]=2; k=2;

    for(i=3;i<=n;i++)
    {
        while ( !convex() && k>2 ) k--;
        s[++k]=i;
    }

    printf("%d\n",k);

    for(i=1;i<=k;i++)
        printf("%0.6lf %0.6lf\n",v[s[i]].x,v[s[i]].y);
    return 0;
}