Cod sursa(job #529173)

Utilizator giuliastefGiulia Stef giuliastef Data 4 februarie 2011 14:17:31
Problema Infasuratoare convexa Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 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;    
     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;
      }
     }
     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++)
     {
      if(a[i].x==xo && a[i].y==yo) continue;
      while(convex(st[k],st[k-1],i)>0 && k>=2) k--;
      st[++k]=i;
     }
}
int main()
{
    citire();
    rezolva();
    scrie();
    return 0;
}