Cod sursa(job #913936)

Utilizator Bogdan13Bogdan Stoian Bogdan13 Data 13 martie 2013 20:51:56
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include<fstream>
#include<algorithm>
#include<iomanip>
#define NMAX 120005
using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

long N,i1,st[NMAX],k;
struct pct{double x,y;}P[NMAX];

double x1,y1;

bool cmp(pct p1,pct p2)
{
    return  (p1.y-y1)*(p2.x-x1) < (p2.y-y1)*(p1.x-x1)   ;
}

bool pl(long i ,long j , long k1)
{
    return ( (P[i].x*P[j].y)+(P[j].x*P[k1].y)+(P[i].y*P[k1].x)-(P[j].y*P[k1].x)-(P[k1].y*P[i].x)-(P[i].y*P[j].x) ) > 0 ;
}

void infas()
{
    st[1]=1;
    k=1;
    for (int i=2;i<=N;i++)
    {
        while(k>1&&pl(st[k],st[k-1],i)) k--;

        st[++k]=i;
    }


}


int main()
{
    f>>N;
    x1=1000000001;
    for (long i=1;i<=N;i++)
    {
        f>>P[i].x>>P[i].y;
        if (P[i].x==x1&&P[i].y<y1) {x1=P[i].x; y1=P[i].y; i1=i;}
        if (P[i].x<x1) {x1=P[i].x; y1=P[i].y; i1=i;}
    }

    pct aux;
    aux=P[i1];
    P[i1]=P[1];
    P[1]=aux;

    sort(P+2,P+N+1,cmp);
    P[++N]=P[1];

    infas();
    g<<k-1<<'\n';

    for (int i=2;i<=k;i++)
    g<<setprecision(6)<<fixed<<P[st[i]].x<<" "<<P[st[i]].y<<'\n';

return 0;
}