Cod sursa(job #1519831)

Utilizator mikeshadowIon Complot mikeshadow Data 7 noiembrie 2015 21:47:46
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 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-1,a[0].y});
		hull.push_back(a[0]);
		
		sort(a+1,a+n,[=](pp x, pp y){ return  ccw(a[0],x,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;
}