Cod sursa(job #2738910)

Utilizator NashikAndrei Feodorov Nashik Data 6 aprilie 2021 15:21:08
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
//#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
struct Point{
    double x;
    double y;
}v[120005];

double Cross_Product(Point a,Point b,Point c){
    return (a.x-b.x)*(a.y-c.y)-(a.y-b.y)*(a.x-c.x);
}
bool mysort(Point a,Point b){
    return (Cross_Product(v[1],a,b)>=0);
}

int sta[120005];
int main()
{
    int n,mini=1,cnt=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>v[i].x>>v[i].y;
        if(v[mini].y>v[i].y){
            mini=i;
        }
    }
    swap(v[1],v[mini]);
    sort(v+2,v+n+1,mysort);
    v[++n]=v[1];
    sta[++cnt]=1;
    for(int i=2;i<=n;i++){
        while(cnt>1){
            if(Cross_Product(v[sta[cnt-1]],v[sta[cnt]],v[i])<=0){
                cnt--;
            }
            else
                break;
        }
        sta[++cnt]=i;
    }
    cnt--;
    cout<<cnt<<"\n";
    for(int i=1;i<=cnt;i++){
        cout<<fixed<<setprecision(6)<<v[sta[i]].x<<" "<<v[sta[i]].y<<"\n";
    }
    return 0;
}