Cod sursa(job #1474631)

Utilizator mikeshadowIon Complot mikeshadow Data 22 august 2015 14:57:48
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long double ld;
 
struct point
{
    ld x,y;
};
 
typedef point pp;
 
struct ConvexHull
{
    vector<pp> hull;
    int m;
     
    ConvexHull(): m(0) {hull.clear();}
     
    bool ccw(pp x, pp y, pp z)
    {
        return  ( (y.x-x.x)*(z.y-x.y) > (y.y - x.y)*(z.x - x.x));
    }
     
    void MakeHull(int n, pp a[])
    {
        hull.clear();
        if (!n) return;
        int x=0;
        for (int i=0; i<n; i++)
            if ( (a[i].y==a[x].y)?a[i].x<a[x].x:a[i].y<a[x].y)
                x=i;
        swap(a[0],a[x]);
         
		hull.push_back({a[0].x,a[0].y+1});
        hull.push_back(a[0]);
         
        sort(a+1,a+n,[=](pp x, pp y){ return (((x.y-a[0].y)*(y.x - a[0].x)) <  (x.x - a[0].x)*(y.y-a[0].y )); });
         
        m = 1;
         
        for (int i=1; i<n; i++)
        {
            while (!ccw(hull[m-1],hull[m],a[i]))
                if (m>1) hull.pop_back(),m--;
                else if (i+1==n) break;
                else i++;
            hull.push_back(a[i]);
            m++;
        }
         
        hull.erase(hull.begin());
    }
};
 
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
  
int n;
pp v[120001];
 
ConvexHull cw;
 
int main()
{
    fin>>n;
   
    for (int i=0; i<n; i++)
        {
            pp x;
            fin>>x.x>>x.y;
            v[i]=x;
        }
     
    cw.MakeHull(n,v);
     
    fout<<cw.m<<'\n';
    for (int i=0; i<cw.m; i++)
        fout<<setprecision(9)<<fixed<<cw.hull[i].x<<' '<<cw.hull[i].y<<'\n';
     
    return 0;
}