Cod sursa(job #2442740)

Utilizator Leonard123Mirt Leonard Leonard123 Data 25 iulie 2019 10:12:30
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <fstream>
#include<algorithm>
#include<vector>
#include<iomanip>
using namespace std;
ifstream cin("nim.in");
ofstream cout("nim.out");
#define maxn 130005
#define x first
#define y second
int head=1, N;
typedef pair<double,double>point;
point v[maxn],ans[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]=v[1];
    ans[2]=v[2];
    head=2;
    for(int i=3; i<=N; i++){
        while(head>=2&&angle_Check(ans[head-1],ans[head],v[i])>0)
            head--;
        ans[++head]=v[i];
    }
    cout<<head<<'\n';
    for(int i=1; i<=head; i++)
        cout<<fixed<<setprecision(9)<<ans[i].x<<' '<<ans[i].y<<'\n';
}

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