Cod sursa(job #2337487)

Utilizator BotzkiBotzki Botzki Data 6 februarie 2019 14:20:24
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.84 kb
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int NMAX=120000;
const double eps=1.0e-14;
//Infasuratoarea convexa pentru oricare 3 puncte necoliniare
struct POINT
{
    double x, y;
};
POINT v[NMAX+5], ll;
int st[NMAX+5];
//ll- low low, cel mai de jos punct si in caz de egalitate cel mai din stanga
double cp(POINT p1, POINT p2, POINT p3)
{
    return (p2.x-p1.x)*(p3.y-p2.y)-(p2.y-p1.y)*(p3.x-p2.x);
}
int ccw(POINT p1, POINT p2, POINT p3)
{
    double vcp;
   vcp=cp(p1, p2, p3);
   if(fabs(vcp)<eps)
    return 0;
   if(vcp>=eps)
    return 1;
   return -1;
}
bool cmp(POINT p1, POINT p2)
{
    //1 daca nu se schimba si 0 daca se schimba
    int vccw=ccw(ll, p1, p2);
    if(vccw>0)
        return 1;
    else
        return 0;
}
int main()
{
    POINT p;
    int n, i, top;
    double a, b;
    fin>>n;
    fin>>a>>b;
    v[0].x=a;
    v[0].y=b;
    for(i=1;i<n;i++)
    {
        fin>>a>>b;
        v[i].x=a;
        v[i].y=b;
        if((v[i].y-v[0].y<=-eps) or (fabs(v[i].y-v[0].y)<eps and v[i].x-v[0].x<=-eps))
           //daca y actual e mai mic decat y lui v[0] sau y sunt egali , am nevoie de cel care are x mai mic
            swap(v[0], v[i]);
    }
    ll=v[0];
    sort(v+1, v+n, cmp);
    v[n]=ll;
    st[1]=0;
    st[2]=1;
    top=2;
    i=2;
    while(i<=n)
    {
        if(ccw(v[st[top-1]], v[st[top]], v[i])>0)
        {
            st[++top]=i;
            i++;
        }
        else
            top--;
    }
    top--;
    //in vardful stivei il am pe ll dar si la inceputul stivei
    fout<<fixed<<showpoint;
    fout<<setprecision(7);
    fout<<top<<"\n";
    for(i=1;i<=top;i++)
        fout<<v[st[i]].x<<" "<<v[st[i]].y<<"\n";
    return 0;
}