Cod sursa(job #1618947)

Utilizator DragodanAlexandraDragodan Alexandra DragodanAlexandra Data 28 februarie 2016 10:09:19
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <iostream>
#include<fstream>
#include<iomanip>
#include<algorithm>
#include<vector>
#define point pair<double,double>

using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int  n,st[120002],top=0,start;
pair<double,double>p[120002];

double det( point x,point y,point z)
{
    return (y.first-x.first)*(z.second-x.second)-(z.first-x.first)*(y.second-x.second);
}

double cmp(point x,point y)
{
    return det(p[1],x,y)>0;
}

void citire()
{
    f>>n;
    start=1;
    for(int i=1;i<=n;i++)
    {
        f>>p[i].first>>p[i].second;
        if(p[i].second<p[start].second) start=i;
        else if(p[i].second==p[start].second and p[i].first<p[start].first) start=i;
    }
}

void rezolvare()
{
    swap(p[1],p[start]);
    sort(p+2,p+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        while(top>=2 and det(p[i],p[st[top]],p[st[top-1]])>0 ) top--;
        st[++top]=i;
    }
}

void afisare()
{
    g<<top<<"\n";
    for(int i=1;i<=top;i++)
    g<<fixed<<setprecision(6)<<p[st[i]].first<<" "<<p[st[i]].second<<"\n";
}
int main()
{
    citire();
    rezolvare();
    afisare();
    return 0;
}