Cod sursa(job #1414383)

Utilizator rangerChihai Mihai ranger Data 2 aprilie 2015 16:11:23
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include<fstream>
#include<algorithm>
#include<vector>
#include<iomanip>
using namespace std;

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

const int N=120004;
const double  inf=1000000000;
#define pb push_back

int n,i,pos;
struct point{
  double x,y, panta; };
bool cmp(point a, point b) { return a.panta < b.panta; }

point a[N],p;
vector<point> sol;

int cp(point _1, point _2, point _3)
{
    return _1.x*_2.y + _2.x*_3.y + _3.x*_1.y -
           _1.y*_2.x - _2.y*_3.x - _3.y*_1.x;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin>>n;
    for (i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
    p=a[1]; pos=1;
    for (i=2;i<=n;i++)
        if (a[i].x<p.x || (a[i].x==p.x && a[i].y<p.y)) p=a[i], pos=i;
    swap(a[1],a[pos]);

    for (i=2;i<=n;i++) a[i].panta=(a[i].x==a[1].x)?inf:(a[i].y-a[1].y)/(a[i].x-a[1].x);

    sort(a+2,a+n+1,cmp);
    sol.pb(a[1]);
    sol.pb(a[2]);
    for (i=3;i<=n;i++){
        while (sol.size()>=2 & cp(sol[sol.size()-1],sol[sol.size()-2],a[i])>=0) sol.pop_back();
        sol.pb(a[i]);
    }
    cout<<sol.size()<<'\n';
    cout<<fixed<<setprecision(10);
    for (i=0;i<sol.size();i++) cout<<sol[i].x<<' '<<sol[i].y<<'\n';
    return 0;
}