Cod sursa(job #2375071)

Utilizator WayronUrsu Ianis-Vlad Wayron Data 7 martie 2019 22:07:06
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <bits/stdc++.h>
#define Point pair<double, double>
#define x first
#define y second
#define NMAX 120001
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

inline double det(Point O, Point A, Point B){
    return (A.x - O.x)*(B.y - O.y) - (B.x - O.x)*(A.y - O.y);
}
int stiva[NMAX];
Point v[NMAX];

bool comp(Point A, Point B){
    return det(v[1], A, B)>0;
}

int main()
{   int n;
    fin>>n>>v[1].x>>v[1].y;

    for(int i=2; i<=n; i++){
        fin>>v[i].x>>v[i].y;
            if(v[i]<v[1]) swap(v[i], v[1]);
    }

    sort(v+2, v+n+1, comp);

    int  head=0;

    for(int i=1; i<=n; i++){
        while(head>=2 && det(v[stiva[head-1]], v[stiva[head]], v[i])< 0) --head;
        stiva[++head] = i;
    }

    fout<<head<<endl;
    fout<<setprecision(6)<<fixed;

    for(int i=1; i<=head; i++) fout<<v[stiva[i]].x<<" "<<v[stiva[i]].y<<endl;
}