Cod sursa(job #1878369)

Utilizator alexionpopescuPopescu Ion Alexandru alexionpopescu Data 14 februarie 2017 08:02:45
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct point{
    double x,y;
};
point p[120001],st[120001];
int n,vf;
double det(point a, point b, point c){
    return a.x*b.y+a.y*c.x+b.x*c.y-c.x*b.y-b.x*a.y-a.x*c.y;
}
bool cmp(point a,point b){
    return det(p[1],a,b)<0;
}
int main(){
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>p[i].x>>p[i].y;
    fin.close();
    int poz=1;
    for(int i=2;i<=n;i++)
        if(p[i].x<p[poz].x)
            poz=i;
    swap(p[1],p[poz]);
    sort(p+2,p+n+1,cmp);
    st[++vf]=p[1];
    st[++vf]=p[2];
    for(int i=3;i<=n;i++){
        while(vf>=2&&det(st[vf-1],st[vf],p[i])>0)
            vf--;
        st[++vf]=p[i];
    }
    fout<<vf<<"\n";
    for(int i=vf;i>0;i--)
        fout<<fixed<<setprecision(6)<<st[i].x<<" "<<st[i].y<<"\n";
    fout.close();
    return 0;
}