Cod sursa(job #2442671)

Utilizator Leonard123Mirt Leonard Leonard123 Data 24 iulie 2019 19:45:41
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <fstream>
#include<algorithm>
#include<iomanip>
using namespace std;
ifstream cin("nim.in");
ofstream cout("nim.out");
#define maxn 100005
#define x first
#define y second
int head=1, N,ans[maxn];
typedef pair<double,double>point;
point v[maxn];

void read(){
    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])
            head=i;
    swap(v[head],v[1]);
    sort(v+2,v+N+1,cmp);

}
void solve(){
    sort_v();
    ans[1]=1;
    ans[2]=2;
    head=2;
    for(int i=3; i<=N; i++){
        while(head>=2&&angle_Check(v[ans[head-1]],v[ans[head]],v[i])>0)
            head--;
        ans[++head]=i;
    }
    cout<<head<<'\n';
    for(int i=1; i<=head; i++)
        cout<<fixed<<setprecision(9)<<v[ans[i]].x<<' '<<v[ans[i]].y<<'\n';
}

int main()
{
    read();
    solve();
}