Cod sursa(job #1917927)

Utilizator GeanaVladGeana Vlad GeanaVlad Data 9 martie 2017 13:37:58
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <iostream>
#include<fstream>
#include<iomanip>
#include<algorithm>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n,i,st[240010],sz,viz[120011],q;
struct coord
{
    double x,y;
};
coord C[120011];
double det(int i,int j,int k)
{
    double x=C[i].x;
    double y=C[i].y;
    double x2=C[j].x;
    double y2=C[j].y;
    double x3=C[k].x;
    double y3=C[k].y;
    return (x*y2+x2*y3+x3*y-x3*y2-x2*y-x*y3);
}
bool comp(coord a,coord b)
{
    if(a.y==b.y)
        return a.x<b.x;
    return a.y<b.y;
}
int main()
{
    f>>n;
    for(i=1;i<=n;i++)
        f>>C[i].x>>C[i].y;
    sort(C+1,C+n+1,comp);
    st[++sz]=1;
    st[++sz]=2;
    viz[2]=1;
    i=3;
    q=1;
    while(!viz[1])
    {
        while(viz[i])
        {
            if(i==n)
                q=-1;
            i+=q;
        }
        while(sz>=2 && det(st[sz-1],st[sz],i)<0)
        {
            viz[st[sz]]=0;
            sz--;
        }
        st[++sz]=i;
        viz[i]=1;
    }
    g<<sz-1<<'\n';
    for(i=1;i<sz;i++)
        g<<setprecision(7)<<fixed<<C[st[i]].x<<' '<<C[st[i]].y<<'\n';
}