Cod sursa(job #2371440)

Utilizator Teo_1101Mititelu Teodor Teo_1101 Data 6 martie 2019 17:38:16
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>

using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

const int NMAX = 1200002;

vector <int> S;

int N;
struct node
{
    double x,y;
}Node[NMAX];
node NOD;
int poz;
void Read()
{
    NOD.x=NOD.y=2000000000;
    fin>>N;
    for(int i=1;i<=N;++i)
    {
        fin>>Node[i].x>>Node[i].y;
        if(Node[i].y<NOD.y){NOD=Node[i];poz=i;}
        else if(Node[i].y==NOD.y && Node[i].x<NOD.x){NOD=Node[i];poz=i;}
    }
    fin.close();
}
int Orientare(node A,node B,node C)
{
    long long o1=(A.y-B.y)*(B.x-C.x);
    long long o2=(A.x-B.x)*(B.y-C.y);
    return o1<=o2;

}
bool comp(node A,node B)
{
    return Orientare(Node[1],A,B);
}
void Do()
{
    swap(Node[poz],Node[1]);
    sort(Node+2,Node+N+1,comp);
    //for(int i=1;i<=N;++i)cout<<Node[i].x<<" "<<Node[i].y<<"\n";
    S.push_back( 1 );
    S.push_back( 2 );
    S.push_back( 3 );

    for(int i=4;i<=N;++i)
    {
        while( !Orientare(Node[S[S.size()-2]] , Node[S.back()] , Node[i]) )S.pop_back();
        S.push_back(i);
    }
    fout<<S.size()<<"\n";
    for(int i=0;i<S.size();++i)
    fout<<fixed<<setprecision(6)<<Node[S[i]].x<<" "<<Node[S[i]].y<<"\n";
}
int main()
{
    Read();
    Do();
    return 0;
}