Cod sursa(job #870850)

Utilizator costi_.-.Costinnel costi_.-. Data 4 februarie 2013 00:31:05
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.78 kb
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>
#define nmax 12001
#define eps 1e-12
using namespace std;

struct punct{
    double x,y;
};

punct P[nmax],S[nmax],pivot;
int N,M;


double distxy(punct &p1,punct &p2)
{
    return((p2.y-p1.y)*(p2.y-p1.y)+(p2.x-p1.x)*(p2.x-p1.x));
}

double delta(punct &P1,punct &P2,punct &P3)
{
    return(
           (P1.x*P2.y)+(P2.x*P3.y)+(P1.y*P3.x)-(P3.x*P2.y)-(P1.x*P3.y)-(P2.x*P1.y)
           );
}

inline bool compara(punct p1,punct p2)
{
    return (delta(pivot,p1,p2)>0);
}

void citeste()
{
    ifstream f("infasuratoare.in");
    int i;

    f>>N;
    for(i=1;i<=N;i++)
    f>>P[i].x>>P[i].y;

    f.close();
}

void rezolva_Graham()
{
    int i,indice;
    punct aux;

    pivot=P[1],indice=1;
    for(i=2;i<=N;i++)
     {
         if(fabs(P[i].x-pivot.x)<=eps)
          {if(P[i].y<pivot.y)
          {pivot=P[i];
           indice=i;
          }}
          else
          if(P[i].x>pivot.x)
          {
              pivot=P[i];
              indice=i;
          }
     }

     aux=P[1];
     P[1]=P[indice];
     P[indice]=aux;

     sort(P+2,P+N+1,compara);

     S[1]=P[1];
     S[2]=P[2];
     M=2;
     i=3;
     while(i<=N)
     {
         if(delta(S[M-1],S[M],P[i])>0.f)
         {
             S[++M]=P[i];
             i++;
         }
         else
         --M;
     }
}

void scrie()
{
    ofstream g("infasuratoare.out");

    int i;

    g<<fixed;
    g<<M<<'\n';
    g<<setprecision(6);
    g<<S[M].x<<' '<<S[M].y<<'\n';
    for(i=1;i<=M-1;i++)
    g<<S[i].x<<' '<<S[i].y<<'\n';

    g.close();
}

int main()
{
    //cout << "Hello world!" << endl;
    citeste();
    rezolva_Graham();
    scrie();
    return 0;
}