Cod sursa(job #2527736)

Utilizator MihaiB729Bucur Mihai MihaiB729 Data 20 ianuarie 2020 20:37:13
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.29 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

#define cin fin
#define cout fout
/*
*/
const int NMAX=1e5;
float x, y;
int n,k;
struct pct{float x, y;}start;
vector<pct>points;
vector<pct>remain;
pct hull[NMAX];

void read()
{
    fin>>n;
    for(int i=1; i<=n; i++)
    {
        fin>>x>>y;
        points.push_back({x, y});
    }
}

int orientation(pct a, pct b, pct c)
{
    int prod=(b.y-a.y)*(c.x-b.x)-(b.x-a.x)*(c.y-b.y);
    if(prod==0)
        return 0;/// coliniare
    return (prod>0)? 1:-1;///1 - clockwise
}

int modul(pct a, pct b)
{
    return (b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y);
}


bool comp(pct b, pct c)
{
    int o=orientation(start, b, c);
    if(o==0)
    {
        if(start.x<b.x)
            return modul(start, b)<modul(start, c);
        return modul(start, b)>modul(start, c);
    }
    return o==-1;
}



void solve()
{
    /// find the bottom-most, left-most point (start)
    start={NMAX, NMAX};
    for(auto p:points)
        if(p.y<start.y)
            start=p;
        else
        if(p.y==start.y&&p.x<start.x)
            start=p;
    ///

    /// eliminam pct de start
    for(auto p:points)
        if(start.x!=p.x||start.y!=p.y)
            remain.push_back(p);
    ///

    /// sort rest of points by polar angle in counterclockwise order
    sort(remain.begin(), remain.end(), comp);
    ///

    /// delete the elements with equal orientation (convex: angle<180)
    /*
    points=remain;
    remain.clear();
    for(auto p:points)
        if(orientation(start, remain.back(), p)==-1||remain.size()==0)
            remain.push_back(p);
    */
    ///

    /// create convex hull
    //for(auto el:remain)
     //   cout<<el.x<<" "<<el.y<<"\n";
    hull[++k]=start;
    hull[++k]=remain[0];
    hull[++k]=remain[1];
    for(int i=2; i<remain.size(); i++)
    {
        while(orientation(hull[k-1], hull[k], remain[i])==1)
            k--;
        hull[++k]=remain[i];
    }
    ///

    /// print the convex hull
    fout<<k<<"\n";
    fout<<fixed;
    for(int i=1; i<=k; i++)
        fout<<setprecision(9)<<hull[i].x<<" "<<hull[i].y<<"\n";
    ///
}


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

    return 0;
}