Cod sursa(job #1167005)

Utilizator ionelasimonaIonela Simona ionelasimona Data 4 aprilie 2014 09:53:44
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include <iomanip>
#include <fstream>
#include <algorithm>
#include <stack>
#include <cmath>
using namespace std;
struct punct{double x,y;};
punct P[120014],p,st[120014];
int n,k;
double deasupra (punct a, punct b, punct c)
{
    return (a.x*b.y+b.x*c.y+c.x*a.y-c.x*b.y-c.y*a.x-b.x*a.y);
}
inline int cmp(punct a, punct b)
{
    double d=deasupra(P[1],a,b);// daca determina convexsitate
    if (d>0)
        return 1;
    return 0;
}
int main()
{
    int i,ind,j;
    fstream f,g;
    f.open("infasuratoare.in",ios::in);
    g.open("infasuratoare.out",ios::out);
    f>>n;
    p.y=p.x=1000000014;
    for (i=1;i<=n;i++)
    {
        f>>P[i].x>>P[i].y;
        if (P[i].y<p.y||(P[i].y==p.y && P[i].x<p.x))
        {
            p=P[i];
            ind=i;
        }
    }
    swap(P[1],P[ind]);
    sort(P+2,P+n+1,cmp);
    st[++k]=P[1];
    st[++k]=P[2];
    for (i=3;i<=n;i++){
        while (k>=2 && deasupra (st[k-1],st[k],P[i])<0)
            k--;
        st[++k]=P[i];
    }
    g<<k<<"\n"<<fixed;
    for (i=1;i<=k;i++)
        g<<setprecision(6)<<st[i].x<<" "<<st[i].y<<"\n";
}