Cod sursa(job #2321253)

Utilizator triscacezarTrisca Vicol Cezar triscacezar Data 15 ianuarie 2019 21:13:13
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb
#include<bits/stdc++.h>

#define N 120010

#define POINT pair< double , double >

#define X first

#define Y second

#define DET(A,B,C) A.X*B.Y+B.X*C.Y+C.X*A.Y-A.Y*B.X-B.Y*C.X-C.Y*A.X

#define DIST(A,B) (A.X-B.X)*(A.X-B.X)+(A.Y-B.Y)*(A.Y-B.Y)

using namespace std;

ifstream f("infasuratoare.in");

ofstream g("infasuratoare.out");

int n,i,vf,comp(POINT A,POINT B),TRIG(POINT A,POINT B,POINT C);

POINT P[N],ST[N];

double u,v,mic=0.00000001;

void read(),solve(),convex_hull(),prints();

int main()

{

    read();

    solve();

    return 0;

}

void read()

{

    POINT Q;int iq;

    f>>n;

    f>>u>>v;P[0]=make_pair(u,v);

    Q=P[0];iq=0;

    for(i=1;i<n;i++)

    {

        f>>u>>v;P[i]=make_pair(u,v);

        if(P[i]<Q){iq=i;Q=P[i];}

    }

    Q=P[iq];P[iq]=P[0];P[0]=Q;

}

void solve()

{

    sort(P+1,P+n,comp);

    convex_hull();

    g<<vf+1<<'\n';

    for(i=1;i<=vf;i++)

        g<<fixed<<setprecision(10)<<ST[i].X<<' '<<ST[i].Y<<'\n';

    i=0;

    g<<fixed<<setprecision(10)<<ST[i].X<<' '<<ST[i].Y<<'\n';

}

int TRIG(POINT A,POINT B,POINT C)

{

    double delta=DET(A,B,C),AB,AC;

    if(delta>mic)return 1;

    if(delta<-mic)return 0;

    AB=DIST(A,B);AC=DIST(A,C);

    if(AC-AB>mic)return 1;

    return 0;

}

int comp(POINT A,POINT B)

{

    return TRIG(P[0],A,B);

}

void convex_hull()

{

    ST[0]=P[0];ST[1]=P[1];vf=1;

    for(i=2;i<n;i++)

    {

        while(!TRIG(ST[vf-1],ST[vf],P[i]))vf--;

        vf++;ST[vf]=P[i];

    }

}