Cod sursa(job #1075401)

Utilizator andreip1996Paun Andrei andreip1996 Data 8 ianuarie 2014 22:19:01
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

struct punct
{
    double x,y;
}v[120010];

int st[120010],viz[120010];
int n,pas,i;

bool cmp(punct a,punct b)
{
    if (a.y<b.y) return 1;
    if (a.y==b.y &&a.x<b.x) return 1;
    return 0;
}

void modif()
{
    if(pas==1)
      {
          i++;
          if(i==n) pas--;
      }
    else i--;
}

void coeficienti(punct a,punct b, double &aa,double &bb,double &cc)
{
    aa=a.y-b.y;
    bb=b.x-a.x;
    cc=a.x*b.y-b.x*a.y;
}

int semn(punct a,punct b,punct c)
{
    double aa,bb,cc;
    coeficienti(a,b,aa,bb,cc);
    if(aa*c.x+bb*c.y+cc<=0)
    return -1;
    return 1;
}

int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
           scanf("%lf%lf",&v[i].x,&v[i].y);
    sort(v+1,v+n+1,cmp);
    pas=1;
    st[1]=1;
    st[2]=2;
    viz[2]=1;
    i=2;
    int k=2;
    while(i>1)
    {
        while(viz[i])
            modif();
        if(i==0) break;
        while(k>1 && semn(v[st[k-1]],v[st[k]],v[i])==-1)
           {
               viz[st[k]]=0;
               k--;
           }
        k++;
        st[k]=i;
        viz[i]=1;
    }
    printf("%d\n",k-1);
    for(int i=1;i<k;i++)
        printf("%lf %lf\n",v[st[i]].x,v[st[i]].y);
    return 0;
}