Cod sursa(job #529241)

Utilizator giuliastefGiulia Stef giuliastef Data 4 februarie 2011 16:20:37
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 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],ind[NMAX],pi;
double xo,yo;
struct cmp
{
 bool operator () (const int &i,const int &j)
 {
 return (long double)(a[i].x - xo) * (a[j].y - yo) > (long double)(a[j].x - xo) * (a[i].y - yo);
 }
};
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;    
     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)
      {
       xo=a[i].x;
       yo=a[i].y;
       pi=i;
      }
     }
     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;
     for(i=1;i<=n;i++)
     { 
      if(i==pi) continue;
      ind[++ind[0]]=i;
     }
     sort(ind+1,ind+ind[0]+1,cmp());                      
     st[++k]=pi;
     for(i=1;i<=ind[0];i++)
     {
      if(ind[i]==pi) continue;
      while(convex(st[k],st[k-1],ind[i])>0 && k>=2) k--;
      st[++k]=ind[i];
     }
}
int main()
{
    citire();
    rezolva();
    scrie();
    return 0;
}