Cod sursa(job #2523963)

Utilizator victorzarzuZarzu Victor victorzarzu Data 14 ianuarie 2020 21:38:09
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

int n;
struct Point
{
    double x,y;
} a[120001];
int head = 1;

void Read()
{
    double x,y;
    f>>n;
    for(int i=0;i<n;++i)
    {
        f>>x>>y;
        a[i].x = x;
        a[i].y = y;
    }
    f.close();
}

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

bool compare(Point B,Point C)
{
    return cross_product(a[0],B,C) < 0;
}

void Sort()
{
    int pos = 0;
    for(int i=1;i<n;++i)
        if(a[i].x < a[pos].x)
            pos = i;
        else if(a[i].x == a[pos].x && a[i].y < a[pos].y)
            pos = i;
    swap(a[0],a[pos]);
    sort(a+1,a+n,compare);
}

Point s[120001];

void convex_hull()
{
    Sort();
    s[0] = a[0];
    s[1] = a[1];
    for(int i=2;i<n;++i)
        {
            while(head >= 2 && cross_product(s[head-1],s[head],a[i]) > 0)
                --head;
            s[++head] = a[i];
        }
}

void Print()
{
    g<<setprecision(3)<<fixed;
    g<<head+1<<'\n';
    for(int i=head;i>=0;--i)
        g<<s[i].x<<" "<<s[i].y<<'\n';
    g.close();
}

int main()
{
    Read();
    convex_hull();
    Print();
    return 0;
}