Cod sursa(job #2280334)

Utilizator andreiudilaUdila Andrei andreiudila Data 10 noiembrie 2018 14:33:56
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <fstream>
#include <iomanip>
#include <algorithm>

using namespace std;

ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");

struct Point{
double x,y;
}pt[120005],S[120005],aux;

int n,i,vf,poz;


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

bool cmp1 (Point A, Point B)
{
    if(A.x == B.x) return A.y < B.y;
    return A.x < B.x;
}
bool cmp (Point A, Point B){

    return det(pt[1],A,B) < 0;

}
int main()
{

    cin>>n;
    aux.x = 2000000000;
    aux.y = 2000000000;
    for(i=1; i<=n; ++i)
        cin>>pt[i].x>>pt[i].y;

    sort(pt+1,pt+n+1,cmp1);
    sort(pt+2,pt+n+1,cmp);

    S[1] = pt[1];
    S[2] = pt[2];
    S[3] = pt[3];
    vf = 3;

    for(int i=4; i <= n; i++)
    {
        while(det(S[vf-1], S[vf], pt[i]) > 0)
            vf--;

        vf++;
        S[vf] = pt[i];
    }

    cout<<vf<<"\n";
    for(i=vf;i>=1;--i)
        cout<<setprecision(12)<<fixed<<S[i].x<<" "<<S[i].y<<"\n";

    return 0;
}