Cod sursa(job #2238414)

Utilizator cezarzbughinCezar Zbughin cezarzbughin Data 5 septembrie 2018 16:04:52
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include<bits/stdc++.h>
#define N 120010
#define POINT pair< double , double >
#define X first
#define Y second
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);
vector<POINT> P,ST;
double u,v,mic=0.00000001;
int main()
{

    f>>n>>u>>v;
    P.push_back(make_pair(u,v));
    POINT Q=P[0];
    int iq=0;
    for(i=1; i<n; i++)
    {
        f>>u>>v;
        P.push_back(make_pair(u,v));
        if(P[i]<Q)
        {
            iq=i;
            Q=P[i];
        }
    }
    Q=P[iq];
    P[iq]=P[0];
    P[0]=Q;
    sort(P.begin()+1,P.end(),comp);
    ST.push_back(P[0]);
    ST.push_back(P[1]);
    vf=1;
    for(i=2; i<n; i++)
    {
        while(!TRIG(ST[vf-1],ST[vf],P[i]))
        {
            ST.pop_back();
            vf--;
        }
        vf++;
        ST.push_back(P[i]);
    }
    g<<vf+1<<'\n';
    for(auto it:ST)
        g<<fixed<<setprecision(6)<<it.X<<' '<<it.Y<<'\n';
    return 0;
}
int TRIG(POINT A,POINT B,POINT C)
{
    return A.X*B.Y+B.X*C.Y+C.X*A.Y-A.Y*B.X-B.Y*C.X-C.Y*A.X>mic;
}
int comp(POINT A,POINT B)
{
    return TRIG(P[0],A,B);
}