Cod sursa(job #873259)

Utilizator costi_.-.Costinnel costi_.-. Data 6 februarie 2013 23:49:19
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.72 kb
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>
#define nmax 120001
#define eps 1e-6
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+p3.x*p1.y-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(P[i].x==pivot.x)
          {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;

     for(i=3;i<=N;i++)
     {
         while(M>=2 && delta(S[M-1],S[M],P[i])<=0)
         --M;

         S[++M]=P[i];
     }

     //pivot.x=0,pivot.y=0;
     //sort(S+1,S+M+1,compara);
}

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

    int i;

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

    g.close();
}

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