Cod sursa(job #1866585)

Utilizator nurckyeRadu Nitescu nurckye Data 3 februarie 2017 12:42:25
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 2.07 kb
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <fstream>
#define NMAX 101
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n,u;
struct coord{
double x;
double y;
} v[NMAX],stiv[NMAX];// vector de puncte, retine coordonata x si coordonata y

double det(coord a, coord b, coord c) // calculez determinantul si afiseaza semnul lui
{
    return ((a.x*b.y)+(b.x*c.y)+(a.y*c.x)-(c.x*b.y)-(c.y*a.x)-(b.x*a.y));

}
int cmp(coord a,coord b) // compara doua sructuri. Nu imi merge == la structuri (De cercetat)
{
    if(a.x==b.x && a.y==b.y)
        return 1;
    return 0;
}

int poz(int p,int u)  // QUICKSORT (SORTEAZA DUPA pozitia cu punctul de start)
{
    coord piv,c;
    piv=v[p];
    while(p<u)
    {
        if(det(v[1],v[p],v[u])<0)
        {
            c=v[p];
            v[p]=v[u];
            v[u]=c;
        }

         if(cmp(v[p],piv))
            u--;
        else
            p++;
    }
    return p;
}
void quick(int p,int u)
{
    int k;
    if(p<u)
    {
        k=poz(p,u);
        quick(p,k-1);
        quick(k+1,u);
    }
} // FINAL QUICKSORT




void cit()
{
    int i;
    f>>n;
    for(i=1;i<=n;i++)
        {
            f>>v[i].x>>v[i].y;
            if(v[i].x<v[1].x ||(v[i].x==v[1].x &&v[i].y<v[1].y))
            swap(v[1],v[i]);
        }
}
void af()
{

    int i;
    f>>n;
    for(i=1;i<=n;i++)
        g<<v[i].x<<v[i].y<<endl;}
bool comp(coord unu,coord doi)
{
    return det(v[1],unu,doi)>0;
}
void infasur()
{
    int i;
    quick(2,n);

    stiv[1]=v[1];
    stiv[2]=v[2];
    u=2;
    for(i=3;i<=n;i++) // ATENTIE LA N UL ASTA
    {


        while(u>=2 && det(stiv[u-1],stiv[u],v[i])<0)
            u--;
        u++;
        stiv[u]=v[i];
    }
}
void af_rezultat()
{
    int i;
    g<<u<<'\n';
    for(i=1;i<=u;i++)
        {
            g<<fixed<<setprecision(6)<<stiv[i].x<<' '<<stiv[i].y<<'\n';
        }
}


int main()
{
    int i;
    cit();
    infasur();
    af_rezultat();



    return 0;
}