Cod sursa(job #2241925)

Utilizator danielsociuSociu Daniel danielsociu Data 17 septembrie 2018 14:51:50
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <fstream>
#include <vector>
#include <algorithm> //sort
#include <iomanip> //setprecision
std::ifstream cin("infasuratoare.in");
std::ofstream cout("infasuratoare.out");
using namespace std;
#define maxn 130000
#define x first
#define y second
typedef pair <double,double> Point;
Point V[maxn],ans[maxn];
int N,head;

void citire(){
    cin>>N;
    for(int i=1;i<=N;i++){
        cin>>V[i].x>>V[i].y;
    }
}

double angle_Check(Point A,Point B,Point C){
    return ((B.x-A.x)*(C.y-A.y))-((C.x-A.x)*(B.y-A.y));
}
bool cmp(Point A,Point B){
    return angle_Check(V[1],A,B)<0;
}
void sort_v(){
    head=1;
    for(int i=2;i<=N;i++)
        if(V[head]>V[i]) //compara first si dupa second in caz first==first
            head=i;
    swap(V[head],V[1]);
    sort(V+2,V+N+1,cmp); //cmp e un criteriu de comparare in plus
}

void scan_Graham(){
    sort_v();
    ans[1]=V[1];
    ans[2]=V[2];

    for(int i=3;i<=N;i++){
        while(head>=2&&angle_Check(ans[head-1],ans[head],V[i])>0)
            head--;
        ans[++head]=V[i];
    }

}

int main()
{
    citire();
    scan_Graham();
    cout<<fixed; //Couts the float no matter what, with a fixed
    cout<<head-1<<'\n'; //number, in this case 9
    for(int i=head;i>1;i--)
        cout<<setprecision(9)<<ans[i].x<<' '<<ans[i].y<<'\n';
}