Cod sursa(job #2374924)

Utilizator Vlad3108Tir Vlad Ioan Vlad3108 Data 7 martie 2019 21:18:18
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <bits/stdc++.h>
using namespace std;
#define LMAX 120005
#define x first
#define y second
typedef pair<long double,long double> point;
point p[LMAX];
int det(point a,point b,point c){
    return (a.x*b.y+b.x*c.y+c.x*a.y)-(a.y*b.x+b.y*c.x+c.y*a.x);
}
bool cmp(point a,point b){
    return det(p[1],a,b)>0;
}
int top=0,st[LMAX];
int main(){
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    int n;
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>p[i].x>>p[i].y;
        if(i>1&&p[i]<p[1])
            swap(p[i],p[1]);
    }
    sort(p+2,p+n+1,cmp);
    int top=0;
    for(int i=1;i<=n;++i){
        while(top>1&&det(p[st[top-1]],p[st[top]],p[i])<=0)
            --top;
        st[++top]=i;
    }
    cout<<top<<"\n";
    for(int i=1;i<=top;++i)
        cout<<fixed<<setprecision(6)<<p[st[i]].x<<" "<<p[st[i]].y<<"\n";
    return 0;
}