Cod sursa(job #1124336)

Utilizator DenisacheDenis Ehorovici Denisache Data 26 februarie 2014 12:07:50
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n,i;
struct Point
{
    double x,y;
}v[120005];
bool viz[120005];
int st[120005],head;
const double EPS=1e-12;
double cross_product(Point O,Point A,Point B)
{
    return (A.x-O.x)*(B.y-O.y)-(B.x-O.x)*(A.y-O.y);
}
bool cmp(Point A,Point B)
{
    if (A.x==B.x) return A.y<B.y;
    else return A.x<B.x;
}
void solve()
{
    sort(v+1,v+n+1,cmp);
    st[1]=1; st[2]=2; head=2; viz[2]=true;
    for (int i=1,p=1;i>0;i+=(p=(i==n?-p:p)))
    {
        if (viz[i]) continue;
        while (head>=2 && cross_product(v[st[head-1]],v[st[head]],v[i])<EPS)
            viz[st[head--]]=false;
        st[++head]=i;
        viz[i]=true;
    }
    g<<head-1<<"\n";
    g<<setprecision(6)<<fixed;
    for (int i=1;i<head;i++) g<<v[st[i]].x<<" "<<v[st[i]].y<<"\n";
}
int main()
{
    f>>n;
    for (i=1;i<=n;i++)
    {
        f>>v[i].x>>v[i].y;
    }
    solve();
    return 0;
}