Cod sursa(job #528193)

Utilizator giuliastefGiulia Stef giuliastef Data 2 februarie 2011 12:55:09
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 kb
#include <fstream>
#define NMAX 120012
using namespace std;
struct puncte{
       double x,y;
       double m;
       } a[NMAX];
       
int i,st[NMAX],n,k;
double x,y,xo,yo;
       
bool cmp(puncte x,puncte y)
{
     return (double)(x.x - a[0].x) * (y.y - a[0].y) > (double)(y.x - a[0].x) * (x.y - a[0].y);    
}

inline int e_convex(float x1, float y1, float x2, float y2, float x3, float y3)
{
    double d;
    d=(float)x1*y2+x2*y3+x3*y1-x2*y1-x3*y2-x1*y3;
    if(d>=0) return 0;
    return 1;
}

int main()
{
    ifstream f("infasuratoare.in");
    ofstream g("infasuratoare.out");
    f>>n;
    f>>xo>>yo;
    for(i=2;i<=n;i++)
    {
     f>>x>>y;
     if(y<yo) a[++k].x=xo, a[k].y=yo, xo=x, yo=y;
     else
      if(y==yo&&x<xo)  a[++k].x=xo, a[k].y=yo, xo=x, yo=y;
      else
       a[++k].x=x, a[k].y=y;
    }
    a[0].x=xo;
    a[0].y=yo;
    sort(a+1,a+k+1,cmp);
    /*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;
     }
    for(i=0;i<=k;i++)
     cout<<a[i].x<<" "<<a[i].y<<"\n";
    cout<<endl;*/
    st[st[0]=1]=0; 
    for(i=1;i<=k;i++)
    {
     while(!e_convex(a[st[st[0]]].x, a[st[st[0]]].y, a[st[st[0]-1]].x, a[st[st[0]-1]].y,a[i].x, a[i].y)&&st[0]>=2) st[0]--;
     st[++st[0]]=i;
    }  
    g<<st[0]<<"\n";
    for(i=1;i<=st[0];i++)
     g<<a[st[i]].x<<" "<<a[st[i]].y<<"\n";
    f.close();
    g.close();
    return 0;
}