Cod sursa(job #416426)

Utilizator giuliastefGiulia Stef giuliastef Data 12 martie 2010 19:11:17
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include <fstream>
using namespace std;
struct puncte{
       float x,y;
       float m;
       } a[120001],aux;
inline int panta(float x1, float y1, float x2, float y2, float x3, float y3)
{
      float m1,m2;
      m1=(y2-y1)*(x3-x1);
      m2=(y3-y1)*(x2-x1);
      if(m1>m2) return 1;
      if(m1==m2) return -1;
      return 0;
}
int e_convex(float x1, float y1, float x2, float y2, float x3, float y3)
{
    float d;
    d=x1*y2+x2*y3+x3*y1-x2*y1-x3*y2-x1*y3;
    if(d>=0) return 0;
    return 1;
}
int main()
{
    int i,j,st[120001],n,k,k1,e;
    float x,y,x1,y1;
    ifstream f("infasuratoare.in");
    ofstream g("infasuratoare.out");
    f>>n;
    f>>x>>y;
    st[1]=0;
    k=0;
    for(i=2;i<=n;i++)
    {
     f>>x1>>y1;
     if(y1<y) a[++k].x=x, a[k].y=y, x=x1, y=y1;
     else
      if(y==y1&&x1<x)  a[++k].x=x, a[k].y=y, x=x1, y=y1;
      else
       a[++k].x=x1, a[k].y=y1;
    }
    a[0].x=x;
    a[0].y=y;
    for(i=1;i<k;i++)
     for(j=i+1;j<=k;j++)
     {
      e=panta(x,y, a[i].x,a[i].y, a[j].x,a[j].y);
      if(e==1)
       aux=a[i], a[i]=a[j], a[j]=aux;
      else 
       if(e==-1&&a[i].x>a[j].x)
         aux=a[i], a[i]=a[j], a[j]=aux;
     }
    st[2]=1, st[3]=2, k1=3;
    for(i=3;i<=k;i++)
    {
     while(!e_convex(a[st[k1]].x, a[st[k1]].y, a[st[k1-1]].x, a[st[k1-1]].y,a[i].x, a[i].y)&&k1>=2) k1--;
     st[++k1]=i;
    }  
    g<<k1<<"\n";
    for(i=1;i<=k1;i++)
     g<<a[st[i]].x<<" "<<a[st[i]].y<<"\n";
    f.close();
    g.close();
    return 0;
}