Cod sursa(job #2173108)

Utilizator malina2109Malina Diaconescu malina2109 Data 15 martie 2018 20:36:12
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct Punct
{
    double x,y;
};
Punct *p;
Punct pimp;
int n;
vector<Punct> s;
void afiseaza()
{
    for(int i=0; i<s.size(); i++)
        g<<s[i].x<<" "<<s[i].y<<"\n";
}
double CrossProduct(Punct P0,  Punct P1,  Punct P2){
    return (P1.x-P0.x)*(P2.y-P0.y)-(P1.y-P0.y)*(P2.x-P0.x);
}
void stangajos()
{
    for(int i=2; i<=n; i++)
    {

        if(p[i].x<p[1].x) swap(p[1],p[i]);
        else if(p[i].x==p[1].x&&p[i].y<p[1].y) swap(p[1],p[i]);
    }
    //cout<<pimp.x<<" "<<pimp.y;
}
bool functie(Punct A,Punct B)
{
    return CrossProduct(p[1],A,B)<0;
}
void graham()
{
    stangajos();
    sort(p+2,p+n+1,functie);
    s.push_back(p[1]);
    s.push_back(p[2]);
    for(int i=3;i<=n;i++)
    {
        while(s.size()>=2&&CrossProduct(s[s.size()-2],s[s.size()-1],p[i])>0)
            s.pop_back();
        s.push_back(p[i]);
    }
    afiseaza();
}
int main()
{
    f>>n;
     p=new Punct[n+1];

    for(int i=1; i<=n; i++)
        f>>p[i].x>>p[i].y;
        pimp=p[1];
      //  for(int i=1;i<=n;i++)
         //   cout<<p[i].x<<" "<<p[i].y<<"\n";
    graham();
    return 0;
}