Cod sursa(job #529228)

Utilizator giuliastefGiulia Stef giuliastef Data 4 februarie 2011 16:03:37
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#define NMAX 120012
#define INF 1<<30
using namespace std;
struct puncte{
       double x,y;
       }a[NMAX];
int n,k,st[NMAX];
double xo,yo;
bool cmp(puncte x, puncte y)
{
    return (long double)(x.x - a[0].x) * (y.y - a[0].y) > (long double)(y.x - a[0].x) * (x.y - a[0].y);    
}
long double convex(int i,int j, int k)
{
    long double d;
    d=(long double) (a[i].x*a[j].y+a[j].x*a[k].y+a[k].x*a[i].y-a[i].x*a[k].y-a[j].x*a[i].y-a[k].x*a[j].y);
    return d;
}
void citire()
{
     int i,aux;
     ifstream f("infasuratoare.in");
     f>>n;
     xo=yo=INF;
     for(i=1;i<=n;i++)
     {
      f>>a[i].x>>a[i].y;
      if(a[i].y<yo || a[i].y==yo&&a[i].x<xo)
      {
       if(xo!=INF && yo!=INF)
       {
        aux=xo, xo=a[i].x, a[i].x=aux;
        aux=yo, yo=a[i].y, a[i].y=aux;
       }
       else
        xo=a[i].x,yo=a[i].y,i--,n--;
      }
     }
     f.close(); 
}
void scrie()
{
     int i;
     ofstream g("infasuratoare.out");
     g<<k<<"\n";
     for(i=1;i<=k;i++)
      g<<fixed<<setprecision(6)<<a[st[i]].x<<" "<<a[st[i]].y<<"\n";
     g.close();
}
void rezolva()
{
     int i;
     a[0].x=xo;
     a[0].y=yo;
     sort(a+1,a+n+1,cmp);
     st[++k]=0;
     for(i=1;i<=n;i++)
     {
      while(convex(st[k],st[k-1],i)>=0 && k>=2) k--;
      st[++k]=i;
     }
}
int main()
{
    citire();
    rezolva();
    scrie();
    return 0;
}