Cod sursa(job #2376322)

Utilizator AndreiDeltaBalanici Andrei Daniel AndreiDelta Data 8 martie 2019 14:52:36
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <bits/stdc++.h>
#define Dim 120008
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int N,poz,head,S[Dim];
double a,b;


struct point
{
    double x,y;
}V[Dim];

double det(point A,point B,point C)
{
    return (A.x-C.x)*(B.y-C.y)-(A.y-C.y)*(B.x-C.x);
}

bool cmp(point X,point Y)
{
    if(det(X,Y,V[1])<0) return 1;
    else return 0;
}

int main()
{
    f>>N;
    for(int i=1;i<=N;i++)
    {
        f>>a>>b;
        V[i]={a,b};
        if(i==1) poz=1;
        else
        if(b<V[poz].y) poz=i;
        else
        if(b==V[poz].y&&a<V[poz].x) poz=i;
    }
    swap(V[1],V[poz]);
    sort(V+2,V+N+1,cmp);
    S[1]=1;
    S[2]=2;
    head=2;
    for(int i=3;i<=N;i++)
    {
        while(head>=2&&det(V[i],V[S[head-1]],V[S[head]])>0) head--;
        S[++head]=i;
    }
    g<<head<<'\n';
    g<<fixed<<setprecision(12)<<V[S[1]].x<<" "<<V[S[1]].y<<'\n';
    for(int i=head;i>1;i--)
        g<<fixed<<setprecision(12)<<V[S[i]].x<<" "<<V[S[i]].y<<'\n';
    return 0;
}