Cod sursa(job #2495818)

Utilizator turtoieduardEduard Turtoi turtoieduard Data 19 noiembrie 2019 20:57:46
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <vector>
using namespace std;

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

int n,tp;
struct Point {
 
    double x,y;
 
};
vector<Point> p;

int st[120005];

int isLeft(const Point &P,const Point &Q,const Point &R){
 
    return ((Q.x-P.x)*(R.y-P.y)-(Q.y-P.y)*(R.x-P.x)>0);
 
}
 
int cmp(const Point &P,const Point &Q){
 
    return isLeft(p[1],P,Q);
 
}
 
int main(){
 
    fin>>n;
    p.resize(n+1);
    for(int i=1;i<=n;i++)
        fin>>p[i].x>>p[i].y;
 
    for(int i=2;i<=n;i++)
        if(p[1].x>p[i].x || (p[1].x==p[i].x && p[1].y>p[i].y))
                swap(p[1],p[i]);
 
    sort(p.begin() + 2, p.end(), cmp);
    st[1]=1; st[2]=2;
    tp=2;
    for(int i=3;i<=n;i++){
 
        while(tp>=2 && !isLeft(p[st[tp-1]],p[st[tp]],p[i])) --tp;
        st[++tp]=i;
 
    }
 
    fout<<tp<<'\n';
    for(int i=1;i<=tp;i++)
        fout<<fixed<<setprecision(6)<<p[st[i]].x<<' '<<p[st[i]].y<<'\n';
 
}